oj.uz

Submission #29279

# Submission time Handle Problem Language Result Execution time Memory
29279 2017-07-19T01:00:58 Z 김동현(#1164) Meteors (POI11_met) C++14
0 / 100
 16 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, k, l[300010], r[300010], s[300010], e[300010], st[300010], nx[300010];
queue<int> q[300010];
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){
		int fl = 0;
		for(int i = 1; i <= n; i++){
			if(s[i] <= e[i]){
				fl = 1;
				q[(s[i] + e[i]) / 2].push(i);
			}
		}
		if(!fl) break;
		S.ini();
		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]);
			}
			while(!q[i].empty()){
				int c = q[i].front(); q[i].pop();
				ll cs = 0;
				for(int j = st[c]; j; j = nx[j]) 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

met.cpp: In function 'int main()':
met.cpp:27: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:29:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
met.cpp:33: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:34:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
                 ^
met.cpp:35: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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 3 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 6 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 16 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 13 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 6 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 9 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 9 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 3 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -