oj.uz

Submission #29309

# Submission time Handle Problem Language Result Execution time Memory
29309 2017-07-19T02:03:11 Z 윤교준(#1168) Meteors (POI11_met) C++11
74 / 100
 2739 ms 50568 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define MAXN (700005)
#define MAXM (700005)
#define MAXK (700005)
using namespace std;
typedef long long ll;
void myassert(bool chk) { if(!chk) { while(1)puts("ERR!"); exit(-1); } }
struct BIT {
	ll d[MAXM];
	void init() { fill(d, d+MAXM, 0); }
	void upd(int x, ll r) { for(; x < MAXM; x += rb(x)) d[x] += r; }
	ll get(int x) { ll r = 0; for(; x; x -= rb(x)) r += d[x]; return r; }
};
struct Node {
	Node(int idx, int s, int e) : idx(idx), s(s), e(e), x((s+e)/2) {}
	int idx, s, e, x;
	bool operator < (const Node& t) const { return x < t.x; }
};

BIT bit;
vector<int> G[MAXN];
vector<Node> V;
int A[MAXK], B[MAXK], C[MAXK], RI[MAXK];
int D[MAXM], E[MAXN];
int Ans[MAXN];
bool isn[MAXN];
int N, M, K;

void input() {
	scanf("%d%d", &N, &M);
	myassert(1 <= N && N <= 300000);
	myassert(1 <= M && M <= 300000);
	for(int i = 1; i <= M; i++) scanf("%d", &D[i]);
	for(int i = 1; i <= N; i++) scanf("%d", &E[i]);
	for(int i = 1; i <= M; i++) myassert(1 <= D[i] && D[i] <= N);
	for(int i = 1; i <= N; i++) myassert(1 <= E[i] && E[i] <= 1000000000);
	int KK; scanf("%d", &KK);
	myassert(1 <= KK && KK <= 300000);
	for(int a, b, c, ki = 1; ki <= KK; ki++) {
		scanf("%d%d%d", &a, &b, &c);
		myassert(1 <= a && a <= M && 1 <= b && b <= M);
		myassert(1 <= c && c <= 1000000000);
		if(a <= b) {
			K++; A[K] = a; B[K] = b; C[K] = c; RI[K] = ki;
		} else {
			K++; A[K] = a; B[K] = M; C[K] = c; RI[K] = ki;
			K++; A[K] = 1; B[K] = b; C[K] = c; RI[K] = ki;
		}
	}
	myassert(1 <= K && K <= 600006);
}
int main() {
	input();
	//printf("N = %d, M = %d, K = %d\n", N, M, K);
	//for(int i = 1; i <= K; i++) printf("%d : %d %d %d %d\n", i, A[i], B[i], C[i], RI[i]);
	for(int i = 1; i <= M; i++) G[D[i]].pb(i);
	for(int i = 1; i <= K; i++) { bit.upd(A[i], C[i]); bit.upd(B[i]+1, -C[i]); }
	//for(int i = 1; i <= M; i++) printf("%d : %lld\n", i, bit.get(i));
	for(int i = 1; i <= N; i++) {
		ll ret = 0;
		for(int v : G[i]) ret += bit.get(v);
		if(E[i] <= ret) continue;
		isn[i] = true;
	}
	for(int i = 1; i <= N; i++) {
		if(isn[i]) continue;
		V.pb(Node(i, 1, K));
	}
	for(int t = 0; t < 30; t++) {
		bit.init(); sorv(V);
		for(int x = 1, vi = 0; x <= K && vi < sz(V); x++) {
			bit.upd(A[x], C[x]); bit.upd(B[x]+1, -C[x]);
			for(; vi < sz(V) && V[vi].x == x; vi++) {
				if(V[vi].s >= V[vi].e) continue;
				ll ret = 0; int idx = V[vi].idx;
				for(int v : G[idx]) ret += bit.get(v);
				if(E[idx] <= ret) V[vi].e = V[vi].x;
				else V[vi].s = V[vi].x+1;
				V[vi].x = (V[vi].s + V[vi].e) / 2;
			}
		}
	}
	for(Node& v : V) Ans[v.idx] = RI[v.s];
	for(int i = 1; i <= N; i++) {
		if(isn[i] || !Ans[i]) { puts("NIE"); continue; }
		printf("%d\n", Ans[i]);
	}
	return 0;
}

Compilation message

met.cpp: In function 'void input()':
met.cpp:40: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:43:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= M; i++) scanf("%d", &D[i]);
                                                ^
met.cpp:44:48: 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("%d", &E[i]);
                                                ^
met.cpp:47:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int KK; scanf("%d", &KK);
                          ^
met.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
                              ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43724 KB Output is correct
2 Correct 19 ms 43724 KB Output is correct
3 Correct 26 ms 43724 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43724 KB Output is correct
2 Correct 29 ms 43724 KB Output is correct
3 Correct 26 ms 43724 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 43988 KB Output is correct
2 Correct 393 ms 44384 KB Output is correct
3 Correct 296 ms 44720 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 44616 KB Output is correct
2 Correct 383 ms 44632 KB Output is correct
3 Correct 143 ms 45272 KB Output is correct
4 Correct 63 ms 44528 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 44256 KB Output is correct
2 Correct 459 ms 44968 KB Output is correct
3 Correct 176 ms 43724 KB Output is correct
4 Correct 319 ms 44788 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 44016 KB Output is correct
2 Correct 443 ms 44640 KB Output is correct
3 Correct 246 ms 44120 KB Output is correct
4 Correct 416 ms 45388 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2739 ms 50568 KB Output is correct
2 Incorrect 2106 ms 46376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2663 ms 50368 KB Output is correct
2 Incorrect 1303 ms 45860 KB Output isn't correct
3 Halted 0 ms 0 KB -