oj.uz

Submission #29289

# Submission time Handle Problem Language Result Execution time Memory
29289 2017-07-19T01:32:58 Z 윤교준(#1168) Meteors (POI11_met) C++11
74 / 100
 1739 ms 31168 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 (300005)
#define MAXM (300005)
#define MAXK (600005)
using namespace std;
typedef long long ll;
const int MX = 1048576+55;
struct SEG {
	ll d[MX], lz[MX];
	void init() { fill(d, d+MX, 0); fill(lz, lz+MX, 0); }
	void prop(int i, int s, int e) {
		if(!lz[i]) return;
		d[i] += lz[i] * (e-s+1);
		if(s != e) { lz[i*2] += lz[i]; lz[i*2+1] += lz[i]; }
		lz[i] = 0;
	}
	void upd(int p, int q, ll r, int i = 1, int s = 1, int e = MAXN) {
		prop(i, s, e); if(q < p || q < s || e < p) return;
		if(p <= s && e <= q) { lz[i] += r; prop(i, s, e); return; }
		int m = (s+e)/2;
		upd(p, q, r, i*2, s, m); upd(p, q, r, i*2+1, m+1, e);
	}
	ll get(int p, int q, int i = 1, int s = 1, int e = MAXN) {
		prop(i, s, e); if(q < p || q < s || e < p) return 0;
		if(p <= s && e <= q) return d[i];
		int m = (s+e)/2;
		return get(p, q, i*2, s, m) + get(p, q, i*2+1, m+1, e);
	}
};
struct BIT {
	ll d[MAXN];
	void init() { fill(d, d+MAXN, 0); }
	void upd(int x, ll r) { for(; x < MAXN; 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 s, e, x, idx;
	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];
bitset<MAXN> isn;
int N, M, K;

void input() {
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++) scanf("%d", &D[i]);
	for(int i = 1; i <= N; i++) scanf("%d", &E[i]);
	int KK; scanf("%d", &KK);
	for(int a, b, c, ki = 1; ki <= KK; ki++) {
		scanf("%d%d%d", &a, &b, &c);
		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;
		}
	}
}
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 < 20; 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]) { puts("NIE"); continue; }
		printf("%d\n", Ans[i]);
	}
	return 0;
}

Compilation message

met.cpp: In constructor 'Node::Node(int, int, int)':
met.cpp:48:15: warning: 'Node::idx' will be initialized after [-Wreorder]
  int s, e, x, idx;
               ^
met.cpp:48:6: warning:   'int Node::s' [-Wreorder]
  int s, e, x, idx;
      ^
met.cpp:47:2: warning:   when initialized here [-Wreorder]
  Node(int idx, int s, int e) : idx(idx), s(s), e(e), x((s+e)/2) {}
  ^
met.cpp: In function 'void input()':
met.cpp:62: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:63: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:64: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:65: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:67: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 3 ms 24324 KB Output is correct
2 Correct 6 ms 24324 KB Output is correct
3 Correct 9 ms 24324 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24588 KB Output is correct
2 Correct 226 ms 24984 KB Output is correct
3 Correct 196 ms 25320 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 25216 KB Output is correct
2 Correct 206 ms 25232 KB Output is correct
3 Correct 119 ms 25872 KB Output is correct
4 Correct 43 ms 25128 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 24856 KB Output is correct
2 Correct 276 ms 25568 KB Output is correct
3 Correct 99 ms 24324 KB Output is correct
4 Correct 209 ms 25388 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 24616 KB Output is correct
2 Correct 269 ms 25240 KB Output is correct
3 Correct 169 ms 24720 KB Output is correct
4 Correct 296 ms 25988 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1739 ms 31168 KB Output is correct
2 Incorrect 876 ms 26976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1653 ms 30968 KB Output is correct
2 Incorrect 929 ms 26460 KB Output isn't correct
3 Halted 0 ms 0 KB -