Submission #1180838

#TimeUsernameProblemLanguageResultExecution timeMemory
1180838al95ireyizHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++20
100 / 100
1966 ms104968 KiB
// It's the evening of another day. And the end of mine... #pragma GCC optimize("O3") #pragma GCC optimize("fast-math") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("no-stack-protector") #include<bits/stdc++.h> using namespace std; // #include<ext/pb_ds/assoc_container.hpp> \ #include<ext/pb_ds/tree_policy.hpp> \ using namespace __gnu_pbds; \ template<class T> \ using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statisticslmode_update>; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif string sp=" "; #define F ୨୧ #define fr first #define er erase #define sc second #define in insert #define ll long long #define pb push_back #define mkp make_pair #define qll queue<ll> #define dqll deque<ll> #define mll map<ll,ll> #define vll vector<ll> #define pll pair<ll,ll> #define ull unsigned ll #define mne min_element #define mxe max_element #define rs(x)resize(x) #define vpll vector<pll> #define vvll vector<vll> #define pq priority_queue #define len(x)(ll)x.size() #define lcm(x,y)x/__gcd(x,y)*y #define all(x)x.begin(),x.end() #define umll unordered_map<ll,ll> #define lg2(x)(63ll-__builtin_clzll(x)) #define precision(x)fixed<<setprecision(x) #define popcnt(x)(ll)__builtin_popcountll(x) template<typename t1,typename t2>istream&operator>>(istream&is,pair<t1,t2>&x){return is>>x.fr>>x.sc;} template<typename t1,typename t2>ostream&operator<<(ostream&os,pair<t1,t2>&x){return os<<x.fr<<' '<<x.sc;} template<typename t1>istream&operator>>(istream&is,vector<t1>&vc){for(t1&j:vc)is>>j;return is;} template<typename t1>ostream&operator<<(ostream&os,vector<t1>&vc){for(t1&j:vc)os<<j<<sp;return os;} // #define ll int_fast32_t // #define ll int_fast64_t // #pragma GCC optimize("O2") // #pragma GCC target("avx,avx2,fma") // #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") const ll INF=1e9; const ll INFL=1e18; const ll MOD=1e9+7; // const ll MOD=998244353; const ll maxn=1e6+5; ll n,m,k=0; inline void prc(){} ll tree[4*maxn], a[maxn]; void upd(ll x, ll val, ll l=1, ll r=n, ll v=1){ if(l == r){ tree[v] = val; return; } ll md = (l+r)>>1; if(x <= md) upd(x, val, l, md, v<<1); else upd(x, val, md+1, r, v<<1|1); tree[v] = max(tree[v<<1], tree[v<<1|1]); } ll get(ll _l, ll _r, ll l=1, ll r=n, ll v=1){ bool in = _l <= l and r <= _r; bool ot = _l <= r and l <= _r; if(in) return tree[v]; if(ot){ ll md = (l+r)>>1; return max(get(_l, _r, l, md, v<<1), get(_l, _r, md+1, r, v<<1|1)); } return 0; } void _(ll&tt){ cin>>n>>m; vll cv(m); for(ll i=1;i<=n;i++) cin>>a[i]; vvll s(m, vll(4)); for(ll i=0;i<m;i++) cin>>s[i][0]>>s[i][1]>>s[i][2], s[i][3] = i; sort(all(s), [&](auto a, auto b){ if(a[1] != b[1]) return a[1] < b[1]; return a < b; }); stack<ll>st; for(ll i=0;i<m;i++){ ll l = s[i][0], r = s[i][1]; for(ll j=k+1;j<=r;j++){ while(!st.empty() and a[st.top()] <= a[j]) st.pop(); if(!st.empty()) upd(st.top(), a[st.top()] + a[j]); st.push(j); } k = max(k, r); cv[s[i][3]] = (get(l, r) <= s[i][2]); } for(ll i=0;i<m;i++) cout<<cv[i]<<'\n'; } signed main(){ clock_t testcaseruntime=clock(); cin.tie(0)->sync_with_stdio(0); prc(); ll t=1; // cin>>t; for(ll tt=1;tt<=t;tt++){ // cout<<"Case "<<tt<<": "; _(tt); } cerr<<"\n\033[1;31mTime: \033[1;30m"<<(double)(clock()-testcaseruntime)/CLOCKS_PER_SEC<<"\033[1;32m seconds"<<'\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...