| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605641 |
2022-07-25T20:44:29 Z |
1ne |
Meteors (POI11_met) |
C++14 |
|
418 ms |
65536 KB |
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
enum EventType { KTYPE, MTYPE, NTYPE };
struct event {
int type, val, pos, idx;
event(int t, int v, int p, int i) : type(t), val(v), pos(p), idx(i) {}
bool operator< (const event& ot) const {
return make_pair(pos, type) < make_pair(ot.pos, ot.type);
}
};
int n, m, k;
vector< event > events;
long long contains[310000];
int target[310000];
int ans[310000];
void rec(int minq, int maxq, vector<event> &events) {
if (minq == maxq) {
for (event e : events) if (e.type == NTYPE) ans[e.val] = minq;
return;
}
int mid = (minq+maxq)/2;
// process events
long long curval = 0;
for (event e : events) {
if (e.type == NTYPE) contains[e.val] = 0;
if (e.type == MTYPE) {
contains[e.val] += curval;
if (contains[e.val] > 1000000000) contains[e.val] = 1000000000;
}
if (e.type == KTYPE && e.idx <= mid) curval += e.val;
}
// split events into two halves
vector<event> events_left, events_right;
for (event e : events) {
if (e.type == NTYPE || e.type == MTYPE) {
if (contains[e.val] >= target[e.val]) {
events_left.push_back(e);
}
else {
target[e.val] -= contains[e.val];
contains[e.val] = 0;
events_right.push_back(e);
}
}
else {
if (e.idx <= mid) events_left.push_back(e);
else events_right.push_back(e);
}
}
rec(minq, mid, events_left);
rec(mid+1, maxq, events_right);
}
int main() {
scanf("%d %d", &n, &m);
REP(i,n) {
events.emplace_back((int)NTYPE, i, -1, -1);
}
REP(i,m) {
int owner;
scanf("%d", &owner); owner--;
events.emplace_back((int)MTYPE, owner, i, -1);
}
REP(i,n) scanf("%d", &target[i]);
scanf("%d", &k);
REP(i,k) {
int l, r, a;
scanf("%d %d %d", &l, &r, &a); l--; r--;
events.emplace_back((int)KTYPE, a, l, i);
events.emplace_back((int)KTYPE, -a, r+1, i);
if (l > r) {
events.emplace_back((int)KTYPE, a, 0, i);
events.emplace_back((int)KTYPE, -a, m, i);
}
}
sort(events.begin(), events.end());
rec(0, k, events);
REP(i,n) {
if (ans[i] < k) printf("%d\n", ans[i]+1);
else printf("NIE\n");
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
| ^
met.cpp:69:2: note: in expansion of macro 'REP'
69 | REP(i,n) {
| ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
| ^
met.cpp:73:2: note: in expansion of macro 'REP'
73 | REP(i,m) {
| ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
| ^
met.cpp:79:2: note: in expansion of macro 'REP'
79 | REP(i,n) scanf("%d", &target[i]);
| ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
| ^
met.cpp:82:2: note: in expansion of macro 'REP'
82 | REP(i,k) {
| ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
| ^
met.cpp:97:2: note: in expansion of macro 'REP'
97 | REP(i,n) {
| ^~~
met.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d", &owner); owner--;
| ~~~~~^~~~~~~~~~~~~~
met.cpp:79:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | REP(i,n) scanf("%d", &target[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
met.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d %d %d", &l, &r, &a); l--; r--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
724 KB |
Output is correct |
| 2 |
Correct |
2 ms |
724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
16452 KB |
Output is correct |
| 2 |
Correct |
125 ms |
32096 KB |
Output is correct |
| 3 |
Correct |
114 ms |
11120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
12196 KB |
Output is correct |
| 2 |
Correct |
107 ms |
11744 KB |
Output is correct |
| 3 |
Correct |
111 ms |
23456 KB |
Output is correct |
| 4 |
Correct |
30 ms |
10552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
12052 KB |
Output is correct |
| 2 |
Correct |
93 ms |
25796 KB |
Output is correct |
| 3 |
Correct |
67 ms |
8704 KB |
Output is correct |
| 4 |
Correct |
97 ms |
11760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
19916 KB |
Output is correct |
| 2 |
Correct |
94 ms |
18736 KB |
Output is correct |
| 3 |
Correct |
85 ms |
10516 KB |
Output is correct |
| 4 |
Correct |
113 ms |
16860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
418 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
414 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
