Submission #29288

#	Time	Username	Problem	Language	Result	Execution time	Memory
29288		khsoo01	Meteors (POI11_met)	C++11	100 / 100	3906 ms	44344 KiB

met

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 300005;

int n, m, k, a[N], req[N], s[N], e[N];
vector<int> ter[N], swp[N];

struct met {int s, e, x;} b[N];

struct segtree {
	ll v[4*N], lim;
	void init () {
		for(lim=1;lim<=m;lim<<=1);
		for(ll i=2*lim;--i;) v[i] = 0;
	}
	void upd (ll S, ll E, ll X) {
		S += lim; E += lim;
		while(S <= E) {
			if(S%2 == 1) v[S++] += X;
			if(E%2 == 0) v[E--] += X;
			S /= 2; E /= 2;
		}
	}
	ll get (ll P) {
		ll ret = 0; P += lim;
		while(P) {ret += v[P]; P /= 2;}
		return ret;
	}
} seg;

bool can (ll I) {
	ll R = 0;
	for(auto &T : ter[I]) {
		R += seg.get(T);
		if(R >= req[I]) return true;
	}
	return false;
}

bool solve () {
	for(ll i=1;i<=n;i++) {
		if(s[i] == e[i]) continue;
		ll M = (s[i]+e[i])/2;
		swp[M].push_back(i);
	}
	seg.init();
	for(ll i=1;i<=k;i++) {
		if(b[i].s > b[i].e) {
			seg.upd(b[i].s, m, b[i].x);
			seg.upd(1, b[i].e, b[i].x);
		}
		else seg.upd(b[i].s,b[i].e,b[i].x);
		for(auto &T : swp[i]) {
			can(T) ? e[T] = i : s[T] = i+1;
		}
		swp[i].clear();
		swp[i].shrink_to_fit();
	}
	for(ll i=1;i<=n;i++) {
		if(s[i] != e[i]) return true;
	}
	return false;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		scanf("%d",&a[i]);
		ter[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) {
		scanf("%d",&req[i]);
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++) {
		scanf("%d%d%d",&b[i].s,&b[i].e,&b[i].x);
	}
	for(int i=1;i<=n;i++) {
		s[i] = 1; e[i] = k+1;
	}
	while(solve());
	for(int i=1;i<=n;i++) {
		if(s[i] == k+1) puts("NIE");
		else printf("%d\n",s[i]);
	}
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
met.cpp:70:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
met.cpp:74:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&req[i]);
                      ^
met.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
                ^
met.cpp:78:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&b[i].s,&b[i].e,&b[i].x);
                                          ^

• 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