oj.uz

Submission #29286

# Submission time Handle Problem Language Result Execution time Memory
29286 2017-07-19T01:24:13 Z 김현수(#1165) Meteors (POI11_met) C++14
87 / 100
 3643 ms 65536 KB 
#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();
	}
	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

met.cpp: In function 'int main()':
met.cpp:67: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:69:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
met.cpp:73:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&req[i]);
                      ^
met.cpp:75:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
                ^
met.cpp:77: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.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 34532 KB Output is correct
2 Correct 296 ms 36400 KB Output is correct
3 Correct 239 ms 35928 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 35388 KB Output is correct
2 Correct 236 ms 35396 KB Output is correct
3 Correct 276 ms 36640 KB Output is correct
4 Correct 39 ms 35252 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 34860 KB Output is correct
2 Correct 163 ms 36892 KB Output is correct
3 Correct 106 ms 33796 KB Output is correct
4 Correct 253 ms 36252 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 34088 KB Output is correct
2 Correct 226 ms 35400 KB Output is correct
3 Correct 189 ms 34324 KB Output is correct
4 Correct 303 ms 37488 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2966 ms 47164 KB Output is correct
2 Correct 849 ms 36316 KB Output is correct
3 Correct 539 ms 33796 KB Output is correct
4 Correct 3643 ms 63824 KB Output is correct

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2886 ms 46368 KB Output is correct
2 Correct 853 ms 35800 KB Output is correct
3 Correct 476 ms 33796 KB Output is correct
4 Memory limit exceeded 2963 ms 65536 KB Memory limit exceeded