Submission #870039

#	Time	Username	Problem	Language	Result	Execution time	Memory
870039		LOLOLO	Meteors (POI11_met)	C++14	74 / 100	848 ms	37464 KiB

met

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
const int MOD = 1e9+7;

typedef long long ll;
typedef pair<int,int> pii;

int m;
const int MAXN = 3e5+5;
ll BIT[MAXN];
vector<int> mid[MAXN],mem[MAXN];
int reqd[MAXN];
int x[MAXN],y[MAXN],z[MAXN];
int ans[MAXN];
int l[MAXN],r[MAXN];
void update(int idx, int val) {
	while(idx<=m) {
		BIT[idx]+=1LL*val;
		idx+=(idx&-idx);
	}
}
ll query(int idx) {
	ll ret=0;
	while(idx) {
		ret+=BIT[idx];
		idx-=(idx&-idx);
	}
	return ret;
}
int main() {
	// freopen("TASK.in","r",stdin);	
	// freopen("TASK.out","w",stdout);
	int n;
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x;
		scanf("%d",&x);
		mem[x].pb(i);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&reqd[i]);
	int q;
	cin>>q;
	for(int i=1;i<=q;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
	for(int i=1;i<=n;i++) l[i]=1,r[i]=q,ans[i]=-1;
	bool changed=true;
	while(changed) {
		changed=false;
		for(int i=0;i<=q;i++) mid[i].clear();
		for(int i=0;i<=m;i++) BIT[i]=0;
		for(int i=1;i<=n;i++) {
			if(l[i]<=r[i]) {
				mid[l[i]+(r[i]-l[i]+1)/2].pb(i);
			}
		}
		for(int i=1;i<=q;i++) {
			if(x[i]<=y[i]) {
				update(x[i],z[i]);
				update(y[i]+1,-z[i]);
			}
			else {
				update(x[i],z[i]);
				update(1,z[i]);
				update(y[i]+1,-z[i]);
			}
			for(auto it:mid[i]) {
				changed=true;
				ll qu=0;
				for(auto j:mem[it]) qu+=query(j);
				if(qu>=reqd[it]) {
					ans[it]=i;
					r[it]=i-1;
				}
				else l[it]=i+1;
			}
		}
	}
	for(int i=1;i<=n;i++) if(ans[i]==-1) printf("NIE\n");else printf("%d\n",ans[i]);
	return 0;
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
met.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d",&reqd[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
met.cpp:52:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  for(int i=1;i<=q;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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