Submission #748691

#	Time	Username	Problem	Language	Result	Execution time	Memory
748691		jamielim	Meteors (POI11_met)	C++14	100 / 100	1845 ms	46404 KiB

met

#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 (stderr)

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13