Районная олимпиада 2019-2020 информатика

Задача C. Мейрамхана

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Мейрамханада $n$ даяршы бар. Олар $1$-ден $n$-ға дейін нөмірленген. Үстелде $m$ стақан тұр. Олар $1$-ден $m$-ге дейін нөмірленген. Бастапқыда барлық стақан бос. Әр даяршы бірнеше стақанға сусын құюы керек. $i$-ші даяршы $l_i$-ден $r_i$-ге дейінгі стақандарға $x_i$ миллилитр сусын құюы керек. Бір даяршы ұйықтап қалып, стақандарға сусын құюды ұмытып кетті. Одан басқа барлық даяршылар тапсырмаларын орындады. Сізге әр стақандағы сусын мөлшері берілген. Сізге ұйықтап қалу мүмкін даяршылардың тізімін табу керек.

Формат входного файла

Бірінші жолда $n$ және $m$ $(1 <= n, m <= 10^5)$ — даяршылар саны және стақандар саны берілген. Келесі $n$ жолдарда $l_i$, $r_i$ және $x_i$ $(1 <= l_i <= r_i <= m$, $1 <= x_i <= 10^3)$ үш сандар берілген. Келесі жолда $m$ бүтін сандар берілген, $a_1$, $a_2$, $\dots$, $a_m$, мұнда $a_i$ $i$-ші стақандағы сусынның миллилитр санын көрсетеді.

Формат выходного файла

Ұйықтап қалу мүмкін даяршылардың нөмірлерін өсу ретінде шығарыңыз.

Система оценки

Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

1. $1 <= n, m <= 100$. 1-2 нөмердегі тесттер.
2. $1 <= n, m <= 3000$. 3-5 нөмердегі тесттер.
3. $1 <= n, m <= 10^5$. 6-10 нөмердегі тесттер

Пример:

Вход

5 4
1 3 2
2 4 3
1 3 2
3 4 1
3 3 1
2 5 7 4

Ответ

1 3

( Aibar Kuanyshbay )

Комментарий/решение

С новым годом. Не проходит по времяни в 6 том тесте. Буду благодарен, если найдете другие варианты решение. :)

кодты корсету/жасыру

#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> a(m);
    vector<vector<int> > b(n,vector<int>(m));
    fill(a.begin(),a.end(),0);
    for(int i=0;i<n;i++){
        int l,r,x;
        cin>>l>>r>>x;
        for(int j=l-1;j<r;j++) {
            a[j]+=x;
            b[i][j]=x;
        }
    }
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        a[i]=a[i]-x;
    }
    for(int i=0;i<n;i++) {
        int t=0;
        for(int j=0;j<m;j++){
            b[i][j]=a[j]-b[i][j];
            if(b[i][j]==0) t++;
        }
        if(t==m) cout<<i+1<<" ";
    }
    return 0;
}

В своем решение вы полностью проходите по отрезку [l, r]. Это решение будет работать но так как вы делаете это 10^5 раз итоговая асимптотика выходит O(nm), что очень медленно. Задача решается с помощью дерева отрезков или же так как задача без обновлений, то есть офлайн можно итоговый массив получить вот так:

При каждом считывании l, r, x в дополнительном массиве на индексе l добавьте x, в индексе r + 1 отнимите x. Затем поступите префикс сумму по этому массиву и это будет итоговый массив.

кодты корсету/жасыру

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n, m, a[N], b[N], cur[N], l, r, sz;
pair < pii, int > x[N];
vi ans;

int main () {
    start
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> x[i].F.F >> x[i].F.S >> x[i].S;
        cur[x[i].F.F] += x[i].S;
        cur[x[i].F.S + 1] -= x[i].S;
    }
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    int kol = 0;
    for(int i = 1; i <= m; i++) {
        kol += cur[i];
        b[i] += kol;
    }
    for(int i = 1; i <= m; i++) {
        if(b[i] != a[i]) {
            if(l == 0) l = i;
            r = i;
            sz = b[i] - a[i];
        }
        else if(l != 0) break;
    }
    pair < pii, int > check = mp(mp(l, r), sz);
    for(int i = 1; i <= n; i++) {
        if(x[i] == check) ans.pb(i);
    }
    for(auto i : ans) {
        cout << i << ' ';
    }
    return 0;
}

n, m = input().split()

n, m = int(n), int(m)

lrx = [[]for i in range(n)]

for i in range(n):

lrx[i] = input().split()

for j in range(3):

lrx[i][j] = int(lrx[i][j])

a= input().split()

for i in range(len(a)):

a[i] = int(a[i])

a_full = [0]*m

for i in range(n):

l=lrx[i][0]

r=lrx[i][1]

x=lrx[i][2]

for j in range(l-1,r):

a_full[j]+=x

mistake = [0]*3

l = float('inf')

for i in range(m):

if a[i] != a_full[i]:

mistake[2] = a_full[i]-a[i]

if i<l:

mistake[0] = l = i+1

mistake[1]= i+1

maybe=[]

for i in range(n):

if lrx[i][0] == mistake[0] and lrx[i][1] == mistake[1] and lrx [i][2] == mistake[2]:

maybe.append(i+1)

for i in maybe:

print(i)

...

кодты корсету/жасыру

#include <bits/stdc++.h>
// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
// #pragma comment(linker, "/stack:200000000")
using namespace std;
#define all(v) v.begin(),v.end()
#define ll long long
#define sz(s) (int)s.size()
#define F first
#define S second
#define pb push_back
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define go ios_base::sync_with_stdio(false);cin.tie(NULL);
template<class T> bool mi(T& a,const T& b) {
  return (b<a ? a=b, 1:0);
}
template<class T> bool umax(T& a,const T& b) {
  return (a<b ? a=b,1:0);
}
template<class A> void read(vector<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vector<A>& x) {
	for(auto & a : x)read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	for(auto & a : x)read(a);
}
ll binpow (ll a, ll n) {
	ll res=1;
	while (n) {
		if (n&1)res*=a;
		a*=a;
		n>>=1;
	}
	return res;
}
const ll N=1e5+12;
ll a[N];
void solve() {
	ll n, m;
	cin>>n>>m;
	vector<pair<pair<ll, ll>, ll > > v; 
	for(int i=0; i<n; i++) {
		ll l, r;
		cin>>l>>r;
		ll x;
		cin>>x;
		v.pb({{l, r}, x});
		a[l]+=x;
		a[r+1]-=x;
	}
	for(int i=1; i<=m; i++) {
		a[i]=a[i]+a[i-1];
	}
	ll b[m+7];
	ll l1=-1, r1=-1;
	bool ok=0;
	for(int i=1; i<=m; i++) {
		cin>>b[i];
		if (b[i]!=a[i] && !ok) {
			l1=i;
			ok=1;
		}
		if (b[i]==a[i] && ok) {
			r1=i-1;
			break;
		}
	}
	ll x1=a[l1]-b[l1];
	for(int i=0; i<sz(v); i++) {
		if (l1==v[i].F.F && r1==v[i].F.S && x1==v[i].S) {
			cout << i+1 << ' ';
		}
	}
}
signed main() {
	go;
	int t=1;
	//cin>>t;
	while (t--)solve();
}
/*
9 0
6 8 2 9 1 8 10 8 6

*/