| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 347773 |
2021-01-13T11:30:08 Z |
Uncreative |
Meteors (POI11_met) |
C++14 |
|
2541 ms |
63976 KB |
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 300030;
unsigned long long loga[2 * maxn];
void update(int x, int val){
for (; x < 2 * maxn; x += (x & (-x))){
loga[x] += val;
}
}
long long query(int x){
unsigned long long ret = 0;
for (; x > 0; x -= (x & (-x))){
ret += loga[x];
}
return ret;
}
vector<int> d[maxn];
long long p[maxn];
int l[maxn];
int r[maxn];
int a[maxn];
int lo[maxn];
int hi[maxn];
int mid[maxn];
vector<int> mn[maxn];
vector<pair<int, int > > nmn;
int sol[maxn];
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
int x;
cin >> x;
d[x].push_back(i);
}
for (int i = 1; i <= n; i++){
cin >> p[i];
}
int k;
cin >> k;
for (int i = 1; i <= k; i++){
cin >> l[i] >> r[i] >> a[i];
}
for (int i = 1; i <= n; i++){
lo[i] = 1;
hi[i] = k;
mid[i] = (lo[i] + hi[i]) / 2;
mn[mid[i]].push_back(i);
}
//cout << 77 << endl;
int lg = (int)log2((double)k) + 3;
//cout << " " << lg << endl;
for (int j = 0; j < lg; j++){
//cerr << "j " << j << "\n";
for (int i = 1; i <= k; i++){
//cerr << i << "\n";
if (l[i] <= r[i]){
update(l[i], a[i]);
update(r[i] + 1, -a[i]);
}
else {
update(l[i], a[i]);
update(m + 1, -a[i]);
update(1, a[i]);
update(r[i] + 1, -a[i]);
}
for (int t = 0; t < mn[i].size(); t++){
//cerr << "T " << t << endl;
int e = mn[i][t];
unsigned long long z = 0;
for (int f = 0; f < d[e].size(); f++){
z += query(d[e][f]);
}
if (z >= p[e]){
sol[e] = i;
hi[e] = i;
nmn.push_back(make_pair((lo[e] + hi[e]) / 2, e));
}
else {
lo[e] = i + 1;
//cout << "mid " << (lo[i] + hi[i] / 2) << endl;
nmn.push_back(make_pair((lo[e] + hi[e]) / 2, e));
}
}
//cerr << "666" << endl;
mn[i].clear();
//cerr << "777" << endl;
}
for (int t = 0; t < nmn.size(); t++){
mn[nmn[t].first].push_back(nmn[t].second);
}
nmn.clear();
memset(loga, 0, sizeof(loga));
}
for (int i = 1; i <= n; i++){
if (sol[i] > 0){
cout << sol[i] << "\n";
}
else {
cout << "NIE\n";
}
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int t = 0; t < mn[i].size(); t++){
| ~~^~~~~~~~~~~~~~
met.cpp:91:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int f = 0; f < d[e].size(); f++){
| ~~^~~~~~~~~~~~~
met.cpp:94:23: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
94 | if (z >= p[e]){
| ~~^~~~~~~
met.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int t = 0; t < nmn.size(); t++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19180 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19180 KB |
Output is correct |
| 3 |
Correct |
16 ms |
19180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19180 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19180 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
20716 KB |
Output is correct |
| 2 |
Correct |
222 ms |
23016 KB |
Output is correct |
| 3 |
Correct |
165 ms |
22508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
21868 KB |
Output is correct |
| 2 |
Correct |
210 ms |
21996 KB |
Output is correct |
| 3 |
Correct |
231 ms |
23144 KB |
Output is correct |
| 4 |
Correct |
58 ms |
21356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
21152 KB |
Output is correct |
| 2 |
Correct |
244 ms |
23784 KB |
Output is correct |
| 3 |
Correct |
217 ms |
19948 KB |
Output is correct |
| 4 |
Correct |
179 ms |
23016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
20332 KB |
Output is correct |
| 2 |
Correct |
220 ms |
21868 KB |
Output is correct |
| 3 |
Correct |
136 ms |
20460 KB |
Output is correct |
| 4 |
Correct |
236 ms |
24424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1498 ms |
38372 KB |
Output is correct |
| 2 |
Correct |
1146 ms |
24184 KB |
Output is correct |
| 3 |
Correct |
1073 ms |
22380 KB |
Output is correct |
| 4 |
Correct |
2401 ms |
59660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1460 ms |
36836 KB |
Output is correct |
| 2 |
Correct |
845 ms |
24052 KB |
Output is correct |
| 3 |
Correct |
841 ms |
21612 KB |
Output is correct |
| 4 |
Correct |
2541 ms |
63976 KB |
Output is correct |
