oj.uz

Submission #29305

# Submission time Handle Problem Language Result Execution time Memory
29305 2017-07-19T01:59:53 Z kdh9949 Meteors (POI11_met) C++14
100 / 100
 3729 ms 25092 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21936 KB Output is correct
2 Correct 6 ms 21936 KB Output is correct
3 Correct 6 ms 21936 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21936 KB Output is correct
2 Correct 6 ms 21936 KB Output is correct
3 Correct 13 ms 21936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 22076 KB Output is correct
2 Correct 293 ms 22404 KB Output is correct
3 Correct 229 ms 22208 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 22208 KB Output is correct
2 Correct 263 ms 22208 KB Output is correct
3 Correct 326 ms 22404 KB Output is correct
4 Correct 73 ms 22208 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 22076 KB Output is correct
2 Correct 206 ms 22404 KB Output is correct
3 Correct 119 ms 21936 KB Output is correct
4 Correct 266 ms 22404 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21936 KB Output is correct
2 Correct 253 ms 22208 KB Output is correct
3 Correct 216 ms 21936 KB Output is correct
4 Correct 309 ms 22404 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2386 ms 23556 KB Output is correct
2 Correct 1063 ms 21936 KB Output is correct
3 Correct 559 ms 21936 KB Output is correct
4 Correct 3729 ms 25092 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2969 ms 23556 KB Output is correct
2 Correct 996 ms 21936 KB Output is correct
3 Correct 519 ms 21936 KB Output is correct
4 Correct 3399 ms 25092 KB Output is correct