Submission #1129277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129277		KN200711	Meteors (POI11_met)	C++20	74 / 100	851 ms	35808 KiB

met

# include <bits/stdc++.h>
# define ll long long
# define ld long double
# define fi first
# define se second
# define pii pair<int, int>
using namespace std;

const int MXN = 3e5;
int N, M, Q;
ll fen[300001];

void add(int a, ll ad) {
	while(a > 0) {
		fen[a] += ad;
		a -= a&(-a);
	}
}

ll qr(int a) {
	ll as = 0ll;
	while(a <= MXN) {
		as += fen[a];
		a += a&(-a);
	}
	return as;
}

vector<int> pl[300001];
ll target[300001];
int L[300001], R[300001], ans[300001];

vector< pair<pii, ll> > qry;
vector<int> ask[300001];

int main() {
	scanf("%d %d", &N, &M);
	for(int i=1;i<=M;i++) {
		int a;
		scanf("%d", &a);
		pl[a].push_back(i);
	}
	
	for(int i=1;i<=N;i++) {
		scanf("%lld", &target[i]);
	}
	
	int Q;
	scanf("%d", &Q);
	for(int i=0;i<Q;i++) {
		int l, r;
		ll val;
		scanf("%d %d %lld", &l, &r, &val);
		qry.push_back({{l, r}, val});
	}
	
	for(int i=1;i<=N;i++) {
		L[i] = 0, R[i] = Q-1, ans[i] = -1;
	}
	
	for(int i=0;i<25;i++) {
		for(int k=0;k<=MXN;k++) fen[k] = 0ll;
		for(int k=0;k<Q;k++) ask[k].clear();
		
		for(int k=1;k<=N;k++) {
			if(L[k] <= R[k]) {
				int mid = (L[k] + R[k]) / 2;
				ask[mid].push_back(k);
			}
		}
		
		for(int k=0;k<Q;k++) {
			int l = qry[k].fi.fi, r = qry[k].fi.se;
			ll val = qry[k].se;
			
			if(l <= r) {
				add(r, val);
				add(l - 1, -val);
			} else {
				add(M, val);
				add(l - 1, -val);
				
				add(r, val);
			}
			
			for(auto p : ask[k]) {
				ll cek = 0ll;
				for(auto c : pl[p]) cek += qr(c);
				if(cek >= target[p]) {
					ans[p] = k;
					R[p] = k - 1;
				} else L[p] = k + 1;
			//	cout<<"p, k : "<<p<<" "<<k<<" "<<cek<<endl;
			}
		}
	}
	
	for(int k=1;k<=N;k++) {
		if(ans[k] == -1) printf("NIE\n");
		else printf("%d\n", ans[k] + 1);
	}
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                 scanf("%d", &a);
      |                 ~~~~~^~~~~~~~~~
met.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |                 scanf("%lld", &target[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~
met.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
met.cpp:53:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |                 scanf("%d %d %lld", &l, &r, &val);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13