Submission #979409

#TimeUsernameProblemLanguageResultExecution timeMemory
979409MDarioIntergalactic ship (IZhO19_xorsum)C++11
0 / 100
1 ms6492 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define all(x) (x).begin(),(x).end() #define MAXN 1000001 using namespace std; using namespace __gnu_pbds; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> TREE; int a[MAXN],arr[MAXN]; int abi[MAXN]; void update(int i,int &k){ while(i < MAXN){ abi[i] += k; i += (i&(-i)); } } int query(int i){ int su = 0; while(i > 0){ su += abi[i]; i -= (i&(-i)); } return su; } int query(int a,int b){ return query(b)-query(a-1); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,q; cin >> n >> q; for(int i = 1; i <= n; i++){ cin >> arr[i]; } for(int i = 1; i < n; i++){ if(arr[i] < arr[i+1]){ a[i] = 1; }else{ a[i] = 0; } update(i,a[i]); } while(q--){ //int cnt = 0; ll l,r,x; cin >> l >> r >> x; if(x == 0){ if(l == r){ cout << 1 << "\n"; continue; } int qe = query(l,r-1); cout << (qe==(r-l)) << "\n"; continue; } int mx = 0; int mxx = 0; for(int i = l; i <= min(l+1000,r); i++){ if(arr[i] < mxx){ if(mx < mxx+arr[i]){ mx = mxx + arr[i]; } } if(mxx < arr[i])mxx = arr[i]; if(mx > x)break; } if(mx > x){ cout << "0\n"; }else{ cout << "1\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...