oj.uz

Submission #29285

# Submission time Handle Problem Language Result Execution time Memory
29285 2017-07-19T01:22:53 Z 김현수(#1165) Meteors (POI11_met) C++14
74 / 100
 2643 ms 47164 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);
	return R >= req[I];
}

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:64: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:66:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
met.cpp:70:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&req[i]);
                      ^
met.cpp:72:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
                ^
met.cpp:74: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 3 ms 33664 KB Output is correct
2 Correct 6 ms 33664 KB Output is correct
3 Correct 6 ms 33664 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 34532 KB Output is correct
2 Correct 259 ms 36400 KB Output is correct
3 Correct 246 ms 35928 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 35388 KB Output is correct
2 Correct 226 ms 35396 KB Output is correct
3 Correct 286 ms 36640 KB Output is correct
4 Correct 43 ms 35252 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 34860 KB Output is correct
2 Correct 163 ms 36892 KB Output is correct
3 Correct 96 ms 33796 KB Output is correct
4 Correct 229 ms 36252 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 34088 KB Output is correct
2 Correct 233 ms 35400 KB Output is correct
3 Correct 189 ms 34324 KB Output is correct
4 Correct 266 ms 37488 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2459 ms 47164 KB Output is correct
2 Incorrect 969 ms 36316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2643 ms 46368 KB Output is correct
2 Incorrect 973 ms 35800 KB Output isn't correct
3 Halted 0 ms 0 KB -