Submission #587475

#TimeUsernameProblemLanguageResultExecution timeMemory
587475NekoRollyRMQ (NOI17_rmq)C++17
0 / 100
2 ms2644 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+4; struct St{ int n,t[N<<1]; void up(int l,int r,int val){ for (l+=n, r+=n; l<r; l>>=1, r>>=1){ if (l&1) t[l] = max(t[l], val), l++; if (r&1) r--, t[r] = max(t[r], val); } } int que(int i){ int ans = t[i+=n]; for (; i>>=1; ) ans = max(ans, t[i]); return ans; } } d1; int n,q; int a[N],p[N]; int L[N],R[N]; set<int> d2; vector<int> d3[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; d1.n = n; for (int i=0; i<n; i++) R[i] = n-1, p[i] = -1; for (int i=0,l,r,x; i<q; i++){ cin >> l >> r >> x; d1.up(l, r+1, x); L[x] = max(L[x], l), R[x] = min(R[x], r); } for (int i=0; i<n; i++) d3[d1.que(i)].push_back(i); for (int i=0; i<n; i++){ int pos = -1; for (int j : d3[i]) d2.insert(j); auto it = d2.lower_bound(L[i]); if (*it <= R[i]) pos = *it; if (pos == -1){ for (int i=0; i<n; i++) p[i] = -1; break; } p[pos] = i; d2.erase(pos); } for (int i=0; i<n; i++) cout << p[i] << " "; cout << "\n"; return 0; }

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:53:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   53 |  for (int i=0; i<n; i++) cout << p[i] << " "; cout << "\n";
      |  ^~~
rmq.cpp:53:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |  for (int i=0; i<n; i++) cout << p[i] << " "; cout << "\n";
      |                                               ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...