| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 379999 |
2021-03-19T22:39:57 Z |
zecookiez |
Meteors (POI11_met) |
C++17 |
|
1281 ms |
28424 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
long long lim[MAXN];
int left1[MAXN], right1[MAXN], qu[MAXN][3];
vector<int> id[MAXN];
int main() {
cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M; cin >> N >> M;
for(int a, i = 1; i <= M; ++i) cin >> a, id[a].push_back(i);
for(int i = 1; i <= N; ++i) cin >> lim[i];
vector<long long> QT(M + 2, 0);
auto apply = [&](int pos, long long V){
assert(pos != 0);
while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
};
auto update = [&](int L, int R, long long V){
if(M == 1){
QT[1] += V; return;
}
if(L <= R){
apply(L, V); apply(R + 1, -V); return;
}
apply(L, V); apply(1, V); apply(R + 1, -V);
};
auto point = [&](int pos){
if(M == 1) return QT[1];
long long tot = 0;
while(pos) tot += QT[pos], pos &= pos - 1;
return tot;
};
int K; cin >> K;
for(int i = 0; i < K; ++i) cin >> qu[i][0] >> qu[i][1] >> qu[i][2];
for(int i = 1; i <= N; ++i) left1[i] = -1, right1[i] = K;
while(true){
vector<array<int, 2>> queries = {};
for(int i = 1; i <= N; ++i){
if(right1[i] - left1[i] > 1){
queries.push_back({(left1[i] + right1[i]) / 2, i});
}
}
if(queries.empty()) break;
sort(queries.begin(), queries.end());
fill(QT.begin(), QT.end(), 0); int j = 0;
while(j < queries.size() && -1 == queries[j][0]){
int k = queries[j][1];
long long tot = 0;
for(int a : id[k]){
tot += point(a);
}
if(tot >= lim[k]) right1[k] = -1;
else left1[k] = -1;
++j;
}
for(int i = 0; i < K; ++i){
update(qu[i][0], qu[i][1], qu[i][2]);
while(j < queries.size() && i == queries[j][0]){
int k = queries[j][1];
long long tot = 0;
for(int a : id[k]){
tot += point(a);
}
if(tot >= lim[k]) right1[k] = i;
else left1[k] = i;
++j;
}
}
while(j < queries.size() && K == queries[j][0]){
int k = queries[j][1];
long long tot = 0;
for(int a : id[k]){
tot += point(a);
}
if(tot >= lim[k]) right1[k] = K;
else left1[k] = K;
++j;
}
}
for(int i = 1; i <= N; ++i){
if(right1[i] == K) cout << "NIE\n";
else cout << right1[i] + 1 << '\n';
}
return 0;
}
Compilation message
met.cpp: In lambda function:
met.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
| ~~~~^~~~~~~~~~~
met.cpp: In function 'int main()':
met.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | while(j < queries.size() && -1 == queries[j][0]){
| ~~^~~~~~~~~~~~~~~~
met.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while(j < queries.size() && i == queries[j][0]){
| ~~^~~~~~~~~~~~~~~~
met.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | while(j < queries.size() && K == queries[j][0]){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7532 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7532 KB |
Output is correct |
| 3 |
Correct |
7 ms |
7404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7404 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7404 KB |
Output is correct |
| 3 |
Correct |
7 ms |
7552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
141 ms |
11124 KB |
Output is correct |
| 3 |
Correct |
121 ms |
10468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
10396 KB |
Output is correct |
| 2 |
Correct |
114 ms |
10524 KB |
Output is correct |
| 3 |
Correct |
166 ms |
11256 KB |
Output is correct |
| 4 |
Correct |
54 ms |
9404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
9860 KB |
Output is correct |
| 2 |
Correct |
137 ms |
11272 KB |
Output is correct |
| 3 |
Correct |
50 ms |
8556 KB |
Output is correct |
| 4 |
Correct |
130 ms |
10900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
118 ms |
10412 KB |
Output is correct |
| 3 |
Correct |
81 ms |
9964 KB |
Output is correct |
| 4 |
Correct |
172 ms |
11480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1281 ms |
28424 KB |
Output is correct |
| 2 |
Incorrect |
715 ms |
22520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1243 ms |
27592 KB |
Output is correct |
| 2 |
Incorrect |
666 ms |
20980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
