oj.uz

Submission #29292

# Submission time Handle Problem Language Result Execution time Memory
29292 2017-07-19T01:39:19 Z 윤교준(#1168) Meteors (POI11_met) C++11
74 / 100
 1963 ms 31424 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;
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 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];
bool isn[MAXN];
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 < 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;
				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 constructor 'Node::Node(int, int, int)':
met.cpp:25:15: warning: 'Node::idx' will be initialized after [-Wreorder]
  int s, e, x, idx;
               ^
met.cpp:25:6: warning:   'int Node::s' [-Wreorder]
  int s, e, x, idx;
      ^
met.cpp:24: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:39: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:40: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:41: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:42: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:44: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 9 ms 24580 KB Output is correct
2 Correct 6 ms 24580 KB Output is correct
3 Correct 9 ms 24580 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 24844 KB Output is correct
2 Correct 279 ms 25240 KB Output is correct
3 Correct 213 ms 25576 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 25472 KB Output is correct
2 Correct 276 ms 25488 KB Output is correct
3 Correct 146 ms 26128 KB Output is correct
4 Correct 43 ms 25384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 25112 KB Output is correct
2 Correct 309 ms 25824 KB Output is correct
3 Correct 116 ms 24580 KB Output is correct
4 Correct 219 ms 25644 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 24872 KB Output is correct
2 Correct 329 ms 25496 KB Output is correct
3 Correct 183 ms 24976 KB Output is correct
4 Correct 313 ms 26244 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1963 ms 31424 KB Output is correct
2 Incorrect 1012 ms 27232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 31224 KB Output is correct
2 Incorrect 1002 ms 26716 KB Output isn't correct
3 Halted 0 ms 0 KB -