oj.uz

Submission #748288

# Submission time Handle Problem Language Result Execution time Memory
748288 2023-05-26T03:30:29 Z jamezzz Meteors (POI11_met) C++17
100 / 100
 3336 ms 50560 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define pb push_back
#define INF 1023456789
typedef long long ll;
typedef vector<int> vi;

#define maxn 300005

ll seg[maxn<<3];

void reset(int i,int s,int e){
	seg[i]=0;
	if(s!=e){
		int m=(s+e)>>1;
		reset(2*i+1,s,m);
		reset(2*i+2,m+1,e);
	}
}
void up(int i,int s,int e,int x,int y,int v){
	if(s==x&&e==y){seg[i]+=v;return;}
	int m=(s+e)>>1;
	if(y<=m)up(2*i+1,s,m,x,y,v);
	else if(x>m)up(2*i+2,m+1,e,x,y,v);
	else up(2*i+1,s,m,x,m,v),up(2*i+2,m+1,e,m+1,y,v);
}
ll qry(int i,int s,int e,int x){
	if(s==x&&e==x)return seg[i];
	int m=(s+e)>>1;
	if(x<=m)return seg[i]+qry(2*i+1,s,m,x);
	else return seg[i]+qry(2*i+2,m+1,e,x);
}

int n,m,p[maxn],k,l[maxn],r[maxn],a[maxn],ans[maxn];
vi s[maxn];

int main(){
	sf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int o;sf("%d",&o);
		s[o].pb(i);
	}
	vi v;
	for(int i=1;i<=n;++i){
		sf("%d",&p[i]);
		v.pb(i);
		ans[i]=-1;
	}
	sf("%d",&k);
	for(int i=1;i<=k;++i)sf("%d%d%d",&l[i],&r[i],&a[i]);
	queue<tuple<int,int,vi>> q;
	q.push({1,k,v});
	int pv=0;
	while(!q.empty()){
		auto[lo,hi,v]=q.front();
		q.pop();
		if(lo>hi||v.empty())continue;
		int mid=(lo+hi)>>1;
		if(mid<pv)reset(0,1,m),pv=0;
		while(pv<mid){
			++pv;
			if(l[pv]<=r[pv])up(0,1,m,l[pv],r[pv],a[pv]);
			else{
				up(0,1,m,l[pv],m,a[pv]);
				up(0,1,m,1,r[pv],a[pv]);
			}
		}
		vi lv,rv;
		for(int x:v){
			ll tot=0;
			for(int i:s[x]){
				tot+=qry(0,1,m,i);
				if(tot>=p[x])break;
			}
			if(tot>=p[x])lv.pb(x),ans[x]=mid;
			else rv.pb(x);
		}
		q.push({lo,mid-1,lv});
		q.push({mid+1,hi,rv});
	}
	for(int i=1;i<=n;++i){
		if(ans[i]==-1)pf("NIE\n");
		else pf("%d\n",ans[i]);
	}
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:41:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  sf("%d%d",&n,&m);
      |    ^
met.cpp:43:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   int o;sf("%d",&o);
      |           ^
met.cpp:48:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   sf("%d",&p[i]);
      |     ^
met.cpp:52:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  sf("%d",&k);
      |    ^
met.cpp:53:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  for(int i=1;i<=k;++i)sf("%d%d%d",&l[i],&r[i],&a[i]);
      |                         ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 7 ms 7380 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 6 ms 7380 KB Output is correct
3 Correct 7 ms 7380 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 9412 KB Output is correct
2 Correct 275 ms 10500 KB Output is correct
3 Correct 277 ms 10700 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 10128 KB Output is correct
2 Correct 266 ms 10300 KB Output is correct
3 Correct 257 ms 10372 KB Output is correct
4 Correct 62 ms 9548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9764 KB Output is correct
2 Correct 161 ms 11104 KB Output is correct
3 Correct 49 ms 7988 KB Output is correct
4 Correct 268 ms 10840 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9296 KB Output is correct
2 Correct 207 ms 10164 KB Output is correct
3 Correct 220 ms 9712 KB Output is correct
4 Correct 273 ms 11448 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1937 ms 26076 KB Output is correct
2 Correct 178 ms 20332 KB Output is correct
3 Correct 346 ms 10652 KB Output is correct
4 Correct 3336 ms 42140 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2029 ms 25156 KB Output is correct
2 Correct 469 ms 20480 KB Output is correct
3 Correct 76 ms 9676 KB Output is correct
4 Correct 2990 ms 50560 KB Output is correct