Submission #332443

#TimeUsernameProblemLanguageResultExecution timeMemory
332443mat_vHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1863 ms85624 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i)) #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i)) #define mod 998244353 #define xx first #define yy second #define all(a) (a).begin(), (a).end() #define pb push_back #define ll long long #define pii pair<int,int> #define maxn 1000005 using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less) mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int n,m; ll niz[maxn]; int ans[maxn]; struct kveri{ int r; int w; int idx; }; vector<kveri> upit[maxn]; int ri[maxn]; int seg[4 * maxn]; void init(int node, int l, int r){ if(l == r){seg[node] = niz[l]; return;} int mid = (l + r) / 2; init(node * 2, l , mid); init(node * 2 + 1, mid + 1, r); seg[node] = max(seg[node * 2], seg[node * 2 + 1]); } int query(int node, int l, int r, int levo, int desno){ if(r < levo || desno < l)return 0; if(l >= levo && r <= desno)return seg[node]; int mid = (l + r) / 2; return max(query(node * 2, l, mid, levo, desno), query(node * 2 + 1, mid + 1, r, levo, desno)); } int seg2[4 * maxn]; void update(int node, int l, int r, int poz, int val){ if(l == r){ seg2[node] = val; return; } int mid = (l + r) / 2; if(poz <= mid)update(node * 2, l, mid, poz, val); else update(node * 2 + 1, mid + 1, r, poz, val); seg2[node] = max(seg2[node * 2], seg2[node * 2 + 1]); } int query2(int node, int l, int r, int levo, int desno){ if(r < levo || desno < l)return 0; if(l >= levo && r <= desno)return seg2[node]; int mid = (l + r) / 2; return max(query2(node * 2, l, mid, levo, desno), query2(node * 2 + 1, mid + 1, r, levo, desno)); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; ff(i,1,n)cin >> niz[i]; init(1,1,n); ff(i,1,m){ int x,y,z; cin >> x >> y >> z; upit[x].pb({y,z,i}); } stack<pii> s; s.push({niz[n], n}); ff(i,1,n)ri[i] = n+1; fb(i,n-1,1){ if(niz[i] < s.top().xx){ ri[i] = s.top().yy; s.push({niz[i], i}); } else{ while(!s.empty() && s.top().xx <= niz[i]){ s.pop(); } if(!s.empty()){ ri[i] = s.top().yy; } s.push({niz[i], i}); } } fb(i,n,1){ if(!(ri[i] == i+1)){ update(1,1,n,i,niz[i] + query(1,1,n,i+1,ri[i]-1)); } for(auto c:upit[i]){ int tr = query2(1,1,n,i,c.r); if(tr > c.w)ans[c.idx] = 0; else ans[c.idx] = 1; } } ff(i,1,m)cout << ans[i] << "\n"; return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:78:5: note: in expansion of macro 'ff'
   78 |     ff(i,1,n)cin >> niz[i];
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:80:5: note: in expansion of macro 'ff'
   80 |     ff(i,1,m){
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:87:5: note: in expansion of macro 'ff'
   87 |     ff(i,1,n)ri[i] = n+1;
      |     ^~
sortbooks.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
sortbooks.cpp:88:5: note: in expansion of macro 'fb'
   88 |     fb(i,n-1,1){
      |     ^~
sortbooks.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
sortbooks.cpp:104:5: note: in expansion of macro 'fb'
  104 |     fb(i,n,1){
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:114:5: note: in expansion of macro 'ff'
  114 |     ff(i,1,m)cout << ans[i] << "\n";
      |     ^~
#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...