oj.uz

Submission #748691

# Submission time Handle Problem Language Result Execution time Memory
748691 2023-05-26T18:12:58 Z jamielim Meteors (POI11_met) C++14
100 / 100
 1845 ms 46404 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m,k;
int p[300005];
vi met[300005];
pair<ii,int> arr[300005];
int ans[300005];

ll fw[300005];
void upd(int x,int y,int v){
	if(x==0&&y==0)return;
	y++;
	while(y<=m){
		fw[y]-=v;
		y+=(y&(-y));
	}
	while(x<=m){
		fw[x]+=v;
		x+=(x&(-x));
	}
}
ll qry(int x){
	ll ans=0;
	while(x){
		ans+=fw[x];
		x-=(x&(-x));
	}
	return ans;
}

queue<pair<ii,vi> > q;

void pbs(){
	pair<ii,vi> cur=q.front();q.pop();
	int l=cur.fi.fi,r=cur.fi.se;
	vi v=cur.se;
	if(l>r)return;
	if(l==0)memset(fw,0,sizeof(fw));
	int mid=(l+r)/2;
	for(int i=l;i<=mid;i++){
		if(arr[i].fi.fi<=arr[i].fi.se)upd(arr[i].fi.fi,arr[i].fi.se,arr[i].se);
		else{
			upd(arr[i].fi.fi,m,arr[i].se);
			upd(1,arr[i].fi.se,arr[i].se);
		}
	}
	vector<int> v1,v2;
	for(int i:v){
		ll sum=0;
		for(int j:met[i]){
			sum+=qry(j);
			if(sum>=p[i])break;
		}
		if(sum>=p[i]){
			v1.pb(i);
			ans[i]=min(ans[i],mid);
		}else{
			v2.pb(i);
		}
	}
	for(int i=mid+1;i<=r;i++){
		if(arr[i].fi.fi<=arr[i].fi.se)upd(arr[i].fi.fi,arr[i].fi.se,arr[i].se);
		else{
			upd(arr[i].fi.fi,m,arr[i].se);
			upd(1,arr[i].fi.se,arr[i].se);
		}
	}
	if(l<r){
		q.push(mp(mp(l,mid),v1));
		q.push(mp(mp(mid+1,r),v2));
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int o;
	for(int i=1;i<=m;i++){
		scanf("%d",&o);
		met[o].pb(i);
	}
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	scanf("%d",&k);
	for(int i=0;i<k;i++)scanf("%d%d%d",&arr[i].fi.fi,&arr[i].fi.se,&arr[i].se);
	
	for(int i=1;i<=n;i++)ans[i]=k;
	vector<int> v;
	for(int i=1;i<=n;i++)v.pb(i);
	q.push(mp(mp(0,k-1),v));
	while(!q.empty())pbs();
	for(int i=1;i<=n;i++){
		if(ans[i]>=k)printf("NIE\n");
		else printf("%d\n",ans[i]+1);
	}
}
/*
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
*/

Compilation message

met.cpp: In function 'int main()':
met.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
met.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d",&o);
      |   ~~~~~^~~~~~~~~
met.cpp:98:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |  for(int i=1;i<=n;i++)scanf("%d",&p[i]);
      |                       ~~~~~^~~~~~~~~~~~
met.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d",&k);
      |  ~~~~~^~~~~~~~~
met.cpp:100:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  for(int i=0;i<k;i++)scanf("%d%d%d",&arr[i].fi.fi,&arr[i].fi.se,&arr[i].se);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 9 ms 9684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9684 KB Output is correct
2 Correct 7 ms 9712 KB Output is correct
3 Correct 7 ms 9788 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 11788 KB Output is correct
2 Correct 113 ms 13996 KB Output is correct
3 Correct 105 ms 13548 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 12236 KB Output is correct
2 Correct 110 ms 13368 KB Output is correct
3 Correct 111 ms 13912 KB Output is correct
4 Correct 32 ms 11340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 12112 KB Output is correct
2 Correct 95 ms 14304 KB Output is correct
3 Correct 55 ms 12028 KB Output is correct
4 Correct 121 ms 13840 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 11624 KB Output is correct
2 Correct 122 ms 13396 KB Output is correct
3 Correct 73 ms 12872 KB Output is correct
4 Correct 117 ms 14476 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 28012 KB Output is correct
2 Correct 554 ms 30892 KB Output is correct
3 Correct 249 ms 22736 KB Output is correct
4 Correct 1671 ms 44144 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 27436 KB Output is correct
2 Correct 621 ms 29316 KB Output is correct
3 Correct 207 ms 20052 KB Output is correct
4 Correct 1845 ms 46404 KB Output is correct