Submission #347709

#TimeUsernameProblemLanguageResultExecution timeMemory
347709UncreativeMeteors (POI11_met)C++14
0 / 100
1124 ms54720 KiB
#include<iostream> #include<vector> #include<cstring> #include<cmath> using namespace std; const int maxn = 300030; long long loga[maxn]; void update(int x, int val){ for (; x < 2 * maxn; x += (x & (-x))){ loga[x] += val; } } long long query(int x){ 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] = 0; hi[i] = k + 1; 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"; //cout << mn[k].size() << endl; 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]); } /*if (i == 3){ for (int e = 1; e <= 3; e++){ long long z = 0; for (int f = 0; f < d[e].size(); f++){ z += query(d[e][f]); } cout << "Z " << e << " " << z << endl; } }*/ //cerr << "555" << endl; //cerr << "Mn " << mn[i].size() << endl; for (int t = 0; t < mn[i].size(); t++){ //cerr << "T " << t << endl; int e = mn[i][t]; long long z = 0; for (int f = 0; f < d[e].size(); f++){ z += query(d[e][f]); } /*if (e == 1 && i == 3){ cout << "da" << endl; }*/ if (z >= p[e]){ sol[e] = i; hi[e] = i; nmn.push_back(make_pair((lo[i] + hi[i]) / 2, i)); } else { lo[e] = i + 1; //cout << "mid " << (lo[i] + hi[i] / 2) << endl; nmn.push_back(make_pair((lo[i] + hi[i]) / 2, i)); } } //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 (stderr)

met.cpp: In function 'int main()':
met.cpp:98:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for (int t = 0; t < mn[i].size(); t++){
      |                             ~~^~~~~~~~~~~~~~
met.cpp:103:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 for (int f = 0; f < d[e].size(); f++){
      |                                 ~~^~~~~~~~~~~~~
met.cpp:125: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]
  125 |         for (int t = 0; t < nmn.size(); t++){
      |                         ~~^~~~~~~~~~~~
#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...