Submission #1157041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157041		Nuraly_Serikbay	Meteors (POI11_met)	C++17	0 / 100	6093 ms	40840 KiB

met

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define pf push_front
#define F first
#define S second
#define IShowSpeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(a) a.begin(),a.end()
const int N=3e5+10;
const int mod=1e9+7;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
ll a[N],b[N],l[N],r[N],x[N],L[N],R[N],mi[N],t[4*N],md[4*N],ans[N];
vector<ll>g[N],mids[N];

void ah(ll& x) {
	x = min(x,mod);
	return;
}

void push(ll v, ll tl, ll tr) {
	if(tl != tr && md[v]) {
		ll mid = (tl + tr) >> 1;
		md[v+v] += md[v];
		md[v+v+1] += md[v];
		t[v+v] += md[v];
		t[v+v+1] += md[v];
		ah(md[v+v]);
		ah(md[v+v+1]);
		ah(t[v+v]);
		ah(t[v+v+1]);
	}
	md[v] = 0;
}

void upd(ll v, ll tl, ll tr, ll l, ll r, ll x) {
	if(l > tr || tl > r) return;
	if(l <= tl && tr <= r) {
		md[v] += x;
		t[v] += md[v];
		ah(t[v]);
		push(v,tl,tr);
		return;
	}
	push(v,tl,tr);
	ll mid = (tl + tr) >> 1;
	upd(v+v,tl,mid,l,r,x);
	upd(v+v+1,mid+1,tr,l,r,x);
	t[v] = t[v+v] + t[v+v+1];
	ah(t[v]);
}

ll get(ll v, ll tl, ll tr, ll pos) {
	if(tl == tr) return t[v];
	push(v,tl,tr);
	ll mid = (tl + tr) >> 1;
	if(pos <= mid) return get(v+v,tl,mid,pos);
	else return get(v+v+1,mid+1,tr,pos);
}

int main()
{
	IShowSpeed
	ll tt=1;
	//cin>>tt;
	while(tt--)
	{
		ll n,m,q;
		cin>>n>>m;
		for(int i=1;i<=m;i++) {
			cin>>a[i];
			g[a[i]].pb(i);
		}
		for(int i=1;i<=n;i++) cin>>b[i];
		cin>>q;
		for(int i=1;i<=q;i++) cin>>l[i]>>r[i]>>x[i];
		for(int i=1;i<=n;i++) {
			L[i] = 1;
			R[i] = q;
			mi[i] = (q+1) >> 1;
		}
		while(true) {
			bool chk = 0;
			for(int i=1;i<=q;i++) mids[i].clear();
			for(int i=1;i<=n;i++) {
				if(L[i] <= R[i]) {
					chk = 1;
					mi[i] = (L[i] + R[i]) >> 1;
					mids[mi[i]].pb(i);
				}
			}
			if(!chk) break;
			for(int i=1;i<=q;i++) {
				if(l[i] <= r[i]) upd(1,1,m,l[i],r[i],x[i]);
				else {
					upd(1,1,m,l[i],m,x[i]);
					upd(1,1,m,1,r[i],x[i]);
				}
				for(ll ok: mids[i]) {
					ll sum = 0;
					for(ll y: g[ok]) {
						sum += get(1,1,m,y);
						if(sum >= b[ok]) break;
					}
					if(sum >= b[ok]) ans[ok] = i,R[ok] = i - 1;
					else L[ok] = i + 1;
				}
			}
			for(int i=1;i<=q;i++) {
				if(l[i] <= r[i]) upd(1,1,m,l[i],r[i],-x[i]);
				else {
					upd(1,1,m,l[i],m,-x[i]);
					upd(1,1,m,1,r[i],-x[i]);
				}
			}
		}
		for(int i=1;i<=n;i++) {
			if(!ans[i]) cout<<"NIE\n";
			else cout<<ans[i]<<"\n";
		}
	}

}
/*
 
 
 
 
*/

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