| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 380004 |
2021-03-19T22:42:49 Z |
zecookiez |
Meteors (POI11_met) |
C++17 |
|
1244 ms |
31912 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 600005;
long long lim[MAXN], 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:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | while(pos < QT.size()) QT[pos] += V, pos += pos & -pos;
| ~~~~^~~~~~~~~~~
met.cpp: In function 'int main()':
met.cpp:42:59: warning: narrowing conversion of '((left1[i] + right1[i]) / 2)' from 'long long int' to 'int' [-Wnarrowing]
42 | queries.push_back({(left1[i] + right1[i]) / 2, i});
| ~~~~~~~~~~~~~~~~~~~~~~~^~~
met.cpp:48: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]
48 | while(j < queries.size() && -1 == queries[j][0]){
| ~~^~~~~~~~~~~~~~~~
met.cpp:60: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]
60 | while(j < queries.size() && i == queries[j][0]){
| ~~^~~~~~~~~~~~~~~~
met.cpp:71: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]
71 | while(j < queries.size() && K == queries[j][0]){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 3 |
Correct |
11 ms |
14444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14484 KB |
Output is correct |
| 3 |
Correct |
12 ms |
14572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
16620 KB |
Output is correct |
| 2 |
Correct |
149 ms |
17828 KB |
Output is correct |
| 3 |
Correct |
122 ms |
17140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
16924 KB |
Output is correct |
| 2 |
Correct |
117 ms |
16932 KB |
Output is correct |
| 3 |
Correct |
168 ms |
17840 KB |
Output is correct |
| 4 |
Correct |
57 ms |
16284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
16620 KB |
Output is correct |
| 2 |
Correct |
138 ms |
17896 KB |
Output is correct |
| 3 |
Correct |
54 ms |
15724 KB |
Output is correct |
| 4 |
Correct |
129 ms |
17484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
16364 KB |
Output is correct |
| 2 |
Correct |
128 ms |
16932 KB |
Output is correct |
| 3 |
Correct |
85 ms |
16492 KB |
Output is correct |
| 4 |
Correct |
164 ms |
17944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1244 ms |
31912 KB |
Output is correct |
| 2 |
Incorrect |
673 ms |
25280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1235 ms |
31236 KB |
Output is correct |
| 2 |
Incorrect |
740 ms |
25220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
