Submission #347705

#TimeUsernameProblemLanguageResultExecution timeMemory
347705lovro_nidogon1Meteors (POI11_met)C++14
74 / 100
2599 ms65540 KiB
#include<bits/stdc++.h> #define breturn return #define ll long long using namespace std; const int maxn = 300001; ll n, m, o[maxn], p[maxn], a, b, c, q, bn, tour[1048600], laz[1048600], ans[maxn]; vector<pair<ll, pair<ll, ll> > > midl[maxn], quer; vector<pair<ll, pair<ll, pair<ll, ll> > > > nx; vector<ll> v[maxn]; bool done; void upd(ll ax, ll bx, ll val, ll x = 1, ll l = 0, ll r = bn - 1) { if(ax > r or bx < l) breturn; if(l >= ax and r <= bx) { laz[x] += val; breturn; } ll mid = (l + r)/2; upd(ax, bx, val, x * 2, l, mid); upd(ax, bx, val, x * 2 + 1, mid + 1, r); } ll query(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) { if(ax > r or bx < l) breturn 0;; if(l >= ax and r <= bx) { tour[x] += laz[x]; laz[x] = 0; breturn tour[x]; } laz[x * 2] += laz[x]; laz[x * 2 + 1] += laz[x]; laz[x] = 0; ll mid = (l + r)/2; breturn query(ax, bx, x * 2, l, mid) + query(ax, bx, x * 2 + 1, mid + 1, r); } int main() { cin >> n >> m; for(int i = 0; i < m; i++ ) cin >> a, v[a - 1].push_back(i); for(ll i = 0; i < n; i++) cin >> p[i]; cin >> q; bn = (1 << ((ll)log2(m - 1 + (m == 1)) + 1)); for(ll i = 0; i < q; i++) { cin >> a >> b >> c; quer.push_back({c, {a - 1, b - 1}}); } for(ll i = 0; i < n; i++) midl[(int)(q/2)].push_back({i, {0, q}}); while(!done) { for(ll i = 0; i < 2 * bn; i++) tour[i] = 0, laz[i] = 0; for(ll i = 0; i < q; i++) { if(quer[i].second.first > quer[i].second.second) { upd(0, quer[i].second.second, quer[i].first); upd(quer[i].second.first, m - 1, quer[i].first); } else upd(quer[i].second.first, quer[i].second.second, quer[i].first); for(ll j = 0; j < midl[i].size(); j++) { ll y = midl[i][j].first; unsigned ll x = 0; for(ll k = 0; k < v[y].size(); k++) x += query(v[y][k], v[y][k]); ll le = midl[i][j].second.first; ll re = midl[i][j].second.second; ll mid = (le + re)/2; if(x < p[y]) le = mid + 1; else re = mid; mid = (le + re)/2; if(le == re) ans[y] = le; else nx.push_back({mid, {y, {le, re}}}); } while(midl[i].size()) midl[i].pop_back(); } done = !(nx.size()); for(ll j = 0; j < nx.size(); j++) midl[nx[j].first].push_back(nx[j].second); nx.clear(); } for(ll i = 0; i < n; i++) { if(ans[i] == q) cout << "NIE\n"; else cout << ans[i] + 1 << '\n'; } }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:52:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(ll j = 0; j < midl[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
met.cpp:55:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(ll k = 0; k < v[y].size(); k++) x += query(v[y][k], v[y][k]);
      |                   ~~^~~~~~~~~~~~~
met.cpp:59:10: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   59 |     if(x < p[y]) le = mid + 1;
      |        ~~^~~~~~
met.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(ll j = 0; j < nx.size(); j++) midl[nx[j].first].push_back(nx[j].second);
      |                 ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...