# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
29313 |
2017-07-19T02:20:28 Z |
윤교준(#1168) |
Meteors (POI11_met) |
C++11 |
|
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);
^
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |