Submission #1117577

#TimeUsernameProblemLanguageResultExecution timeMemory
1117577vjudge1Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
17 / 100
229 ms33608 KiB
#include <bits/stdc++.h> #define pb push_back #define pf push_front #define ll long long #define F first #define S second #define all(v) (v).begin(),(v).end() #define ull unsigned long long #define int long long #define asdasd ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; mt19937 rng( chrono::steady_clock::now().time_since_epoch().count()); long long rand( long long l, long long r ) { uniform_int_distribution <long long> uid( l, r ); return uid( rng ); } ll lcm(ll x, ll y){ return x / __gcd(x,y) * y; } const int mod = 1e9 + 7; const ll inf = 1e18; const int maxn = 1e6 + 6; int n,m,a[maxn],x[maxn],y[maxn],z[maxn],t[maxn * 4],pref[maxn]; void build(int v = 1, int tl = 1, int tr = n){ if(tl == tr){ t[v] = a[tl]; return; } int tm = (tl + tr) >> 1; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); t[v] = min(t[v + v], t[v + v + 1]); } int get(int l, int r, int v = 1, int tl = 1, int tr = n){ if(tl > r || l > tr) return 2e9; if(l <= tl && tr <= r){ return t[v]; } int tm = (tl + tr) >> 1; return min(get(l,r,v+v,tl,tm),get(l,r,v+v+1,tm+1,tr)); } void solve(){ cin >> n >> m; bool ok1 = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= m; i++){ cin >> x[i] >> y[i] >> z[i]; if(ok1 && get(x[i],y[i]) <= z[i]){ ok1 = 0; } } if(ok1){ for(int i = 1; i <= n; i++){ if(a[i] < a[i - 1]){ pref[i] = 1; } } for(int i = 1; i <= n; i++){ pref[i] += pref[i - 1]; } } if(n <= 5000 && m <= 5000){ for(int i = 1; i <= m; i++){ int l = x[i],r = y[i]; int mx = a[l]; bool ok = 1; for(int j = l+1; j <= r; j++){ if(mx > a[j] && mx + a[j] > z[i]){ ok = 0; break; } mx = max(mx, a[j]); } if(ok){ cout << "1\n"; } else { cout << "0\n"; } } } else if(ok1){ for(int i = 1; i <= m; i++){ int l = x[i],r = y[i]; int xx = pref[r] - pref[l]; if(xx){ cout << "0\n"; } else { cout << "1\n"; } } } } signed main(){ asdasd int tt = 1; while(tt--){ solve(); } return 0; }
#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...