Submission #29305

#	Time	Username	Problem	Language	Result	Execution time	Memory
29305		kdh9949	Meteors (POI11_met)	C++14	100 / 100	3729 ms	25092 KiB

met

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, m, k, l[300010], r[300010], s[300010], e[300010], st[300010], nx[300010];
vector<pii> qv;
ll p[300010], a[300010];

const int sz = 524288;
struct Seg{
	ll dat[2 * sz];
	void ini(){ fill(dat + 1, dat + 2 * sz, 0); }
	void upd(int s, int e, ll v){
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) dat[s++] += v;
			if(e % 2 == 0) dat[e--] += v;
		}
	}
	ll get(int x){
		ll ret = 0;
		for(x += sz; x; x /= 2) ret += dat[x];
		return ret;
	}
} S;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1, x; i <= m; i++){
		scanf("%d", &x);
		nx[i] = st[x];
		st[x] = i;
	}
	for(int i = 1; i <= n; i++) scanf("%lld", p + i);
	scanf("%d", &k);
	for(int i = 1; i <= k; i++) scanf("%d%d%lld", l + i, r + i, a + i);
	fill(s + 1, s + n + 1, 1);
	fill(e + 1, e + n + 1, k);
	while(1){
		qv.clear();
		for(int i = 1; i <= n; i++){
			if(s[i] <= e[i]) qv.push_back(pii((s[i] + e[i]) / 2, i));
		}
		if(qv.empty()) break;
		sort(qv.begin(), qv.end());
		S.ini();
		int t = 0;
		for(int i = 1; i <= k; i++){
			if(l[i] <= r[i]) S.upd(l[i], r[i], a[i]);
			else{
				S.upd(l[i], m, a[i]);
				S.upd(1, r[i], a[i]);
			}
			for(; t < qv.size() && qv[t].first == i; t++){
				int c = qv[t].second;
				ll cs = 0;
				for(int j = st[c]; j; j = nx[j]) cs = min(p[c], cs + S.get(j));
				if(cs >= p[c]) e[c] = i - 1;
				else s[c] = i + 1;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(s[i] > k) puts("NIE");
		else printf("%d\n", s[i]);
	}
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:54:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; t < qv.size() && qv[t].first == i; t++){
            ^
met.cpp:28:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
met.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
met.cpp:34:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%lld", p + i);
                                                  ^
met.cpp:35:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
                 ^
met.cpp:36:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= k; i++) scanf("%d%d%lld", l + i, r + i, a + i);
                                                                    ^

• 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