| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 555113 |
2022-04-30T07:37:25 Z |
IvanJ |
Meteors (POI11_met) |
C++17 |
|
978 ms |
36288 KB |
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 3e5 + 5;
int n, m, k;
vector<int> own[maxn];
ll need[maxn];
pair<ii, int> qs[maxn];
vector<pair<ii, int>> A[maxn];
vector<pair<ii, int>> A1[maxn];
int ans[maxn], ok[maxn];
ll fwt[maxn];
void update(int x, ll v) {
x++;
for(;x < maxn;x += (x & -x)) fwt[x] += v;
}
ll query(int x) {
x++;
ll ret = 0;
for(;x > 0;x -= (x & -x)) ret += fwt[x];
return ret;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0;i < m;i++) {
int x;scanf("%d", &x);x--;
own[x].pb(i);
}
for(int i = 0;i < n;i++) scanf("%lld", need + i);
scanf("%d", &k);
for(int i = 0;i < k;i++) {
int l, r, a;
scanf("%d %d %d", &l, &r, &a);
l--, r--;
qs[i] = {{l, r}, a};
}
for(int i = 0;i < n;i++) {
int mid = (k - 1) / 2;
A[mid].pb({{0, k - 1}, i});
}
while(true) {
for(int i = 0;i < maxn;i++) fwt[i] = 0;
int flag = 0;
for(int i = 0;i < k;i++) {
if(qs[i].x.x > qs[i].x.y) {
update(qs[i].x.x, qs[i].y);
update(m, -qs[i].y);
update(0, qs[i].y);
update(qs[i].x.y + 1, -qs[i].y);
} else {
update(qs[i].x.x, qs[i].y);
update(qs[i].x.y + 1, -qs[i].y);
}
for(pair<ii, int> p : A[i]) {
//cout << i << "->" << p.x.x << ' ' << p.x.y << " (" << p.y << ")\n";
if(p.x.x > p.x.y) {continue;}
flag = 1;
ll sum = 0;
for(int j : own[p.y]) sum += query(j);
//cout << sum << "\n";
pair<ii, int> p1 = p;
if(sum < need[p.y]) {
int mid = i + 1 + (p.x.y - i - 1) / 2;
p1.x.x = i + 1;
if(p1.x.x <= p1.x.y && mid >= 0 && mid < k) A1[mid].pb(p1);
}
if(sum >= need[p.y]) {
int mid = p.x.x + (i - 1 - p.x.x) / 2;
p1.x.y = i - 1;
if(p1.x.x <= p1.x.y && mid >= 0 && mid < k) A1[mid].pb(p1);
ans[p.y] = i + 1;
}
}
}
for(int i = 0;i < k;i++) A[i].clear(), A[i].shrink_to_fit(), A[i] = A1[i], A1[i].clear(), A1[i].shrink_to_fit();
if(!flag) break;
}
for(int i = 0;i < n;i++) {
if(!ans[i]) printf("NIE\n"); else printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | int x;scanf("%d", &x);x--;
| ~~~~~^~~~~~~~~~
met.cpp:41:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | for(int i = 0;i < n;i++) scanf("%lld", need + i);
| ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
met.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d %d %d", &l, &r, &a);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23860 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23860 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
24928 KB |
Output is correct |
| 2 |
Correct |
177 ms |
26264 KB |
Output is correct |
| 3 |
Correct |
125 ms |
25748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
25480 KB |
Output is correct |
| 2 |
Correct |
132 ms |
25432 KB |
Output is correct |
| 3 |
Correct |
163 ms |
26464 KB |
Output is correct |
| 4 |
Correct |
41 ms |
25272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
25160 KB |
Output is correct |
| 2 |
Correct |
160 ms |
26608 KB |
Output is correct |
| 3 |
Correct |
149 ms |
24424 KB |
Output is correct |
| 4 |
Correct |
127 ms |
26092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
24640 KB |
Output is correct |
| 2 |
Correct |
146 ms |
25524 KB |
Output is correct |
| 3 |
Correct |
95 ms |
24808 KB |
Output is correct |
| 4 |
Correct |
158 ms |
26752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
956 ms |
36288 KB |
Output is correct |
| 2 |
Incorrect |
637 ms |
28624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
978 ms |
35792 KB |
Output is correct |
| 2 |
Incorrect |
710 ms |
28632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
