oj.uz

Submission #29313

# Submission time Handle Problem Language Result Execution time Memory
29313 2017-07-19T02:20:28 Z 윤교준(#1168) Meteors (POI11_met) C++11
100 / 100
 3529 ms 40456 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 INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (300005)
#define MAXM (300005)
#define MAXK (600005)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
void myassert(bool chk) { if(!chk) { while(1)puts("ERR!"); exit(-1); } }
struct BIT {
	lll d[MAXM];
	void init() { fill(d, d+MAXM, 0); }
	void upd(int x, lll r) { for(; x < MAXM; x += rb(x)) d[x] += r; }
	lll get(int x) { lll 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() {
	/*
	puts("300000 300000");
	for(int i = 1; i <= 300000; i++) printf("300000 "); puts("");
	for(int i = 1; i <= 300000; i++) printf("1000000000 "); puts("");
	puts("300000");
	for(int i = 1; i <= 300000; i++) puts("2 1 1000000000");
	return 0; */
	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++) {
		lll 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 < 25; 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;
				lll 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]) { puts("NIE"); continue; }
		printf("%d\n", Ans[i]);
	}
	return 0;
}

Compilation message

met.cpp: In function 'void input()':
met.cpp:42: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:45: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:46: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:49: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:52: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 19 ms 26924 KB Output is correct
2 Correct 19 ms 26924 KB Output is correct
3 Correct 19 ms 26924 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 27188 KB Output is correct
2 Correct 326 ms 27584 KB Output is correct
3 Correct 259 ms 27920 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 27816 KB Output is correct
2 Correct 353 ms 27832 KB Output is correct
3 Correct 146 ms 28472 KB Output is correct
4 Correct 53 ms 27728 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 27456 KB Output is correct
2 Correct 406 ms 28168 KB Output is correct
3 Correct 159 ms 26924 KB Output is correct
4 Correct 256 ms 27988 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 27216 KB Output is correct
2 Correct 369 ms 27840 KB Output is correct
3 Correct 203 ms 27320 KB Output is correct
4 Correct 379 ms 28588 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2119 ms 33768 KB Output is correct
2 Correct 316 ms 29576 KB Output is correct
3 Correct 1036 ms 26924 KB Output is correct
4 Correct 3169 ms 39436 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2149 ms 33568 KB Output is correct
2 Correct 1109 ms 29060 KB Output is correct
3 Correct 193 ms 26924 KB Output is correct
4 Correct 3529 ms 40456 KB Output is correct