oj.uz

Submission #410226

# Submission time Handle Problem Language Result Execution time Memory
410226 2021-05-22T10:00:27 Z rrrr10000 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1479 ms 137604 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
class segtree{
    vi seg;ll N=1;
public:
    ll g=-inf;
    ll f(ll a,ll b){
        return max(a,b);
    }
    segtree(ll n,ll k){
        while(N<n)N*=2;
        seg=vi(N*2-1,g);
        rep(i,n)seg[i+N-1]=k;
        for(ll i=N-2;i>=0;i--)seg[i]=f(seg[i*2+1],seg[i*2+2]);
    }
    segtree(vi v){
        while(N<v.size())N*=2;
        seg=vi(N*2-1,g);
        rep(i,v.size())seg[i+N-1]=v[i];
        for(ll i=N-2;i>=0;i--)seg[i]=f(seg[i*2+1],seg[i*2+2]);
    }
    void add(ll i,ll x){
        i+=N-1;
        seg[i]+=x;
        while(i>0){
            i=(i-1)/2;
            seg[i]=f(seg[i*2+1],seg[i*2+2]);
        }
    }
    void update(ll i,ll x){
        i+=N-1;
        seg[i]=x;
        while(i>0){
            i=(i-1)/2;
            seg[i]=f(seg[i*2+1],seg[i*2+2]);
        }
    }
    ll get(ll l,ll r){
        ll res=g;
        l+=N-1;r+=N-1;
        while(l<r){
            if(!(l&1))res=f(res,seg[l]);
            if(!(r&1))res=f(res,seg[r-1]);
            l=l>>1;
            r=(r-1)>>1;
        }
        return res;
    }
    void debug(ll n){
        rep(i,n)cout<<' '<<seg[i+N-1];cout<<endl;
    }
};
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,q;cin>>n>>q;
    vi v(n);rep(i,n)cin>>v[i];
    vi st;
    vvi tmp(n);
    for(int i=n-1;i>=0;i--){
        while(st.size()&&v[st.back()]<v[i]){
            tmp[i].pb(st.back());
            st.pop_back();
        }
        st.pb(i);
    }
    vvi query(n);
    vi ans(q);
    vi r(q),val(q);
    rep(i,q){
        ll l;cin>>l>>r[i]>>val[i];l--;r[i]--;
        query[l].pb(i);
    }
    segtree seg(n,-1);
    for(int i=n-1;i>=0;i--){
        for(ll x:tmp[i])seg.update(x,v[i]+v[x]);
        for(ll x:query[i])if(seg.get(0,r[x]+1)<=val[x])ans[x]=1;
    }
    for(ll x:ans)out(x);
}

Compilation message

sortbooks.cpp: In constructor 'segtree::segtree(vi)':
sortbooks.cpp:64:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while(N<v.size())N*=2;
      |               ~^~~~~~~~~
sortbooks.cpp: In member function 'void segtree::debug(ll)':
sortbooks.cpp:3:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    3 | #define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
      |                    ^~~
sortbooks.cpp:97:9: note: in expansion of macro 'rep'
   97 |         rep(i,n)cout<<' '<<seg[i+N-1];cout<<endl;
      |         ^~~
sortbooks.cpp:97:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |         rep(i,n)cout<<' '<<seg[i+N-1];cout<<endl;
      |                                       ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 564 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 6 ms 1100 KB Output is correct
15 Correct 5 ms 1100 KB Output is correct
16 Correct 4 ms 1100 KB Output is correct
17 Correct 4 ms 844 KB Output is correct
18 Correct 4 ms 980 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1435 ms 137604 KB Output is correct
2 Correct 1432 ms 135612 KB Output is correct
3 Correct 1479 ms 135624 KB Output is correct
4 Correct 1395 ms 135620 KB Output is correct
5 Correct 1293 ms 124752 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16332 KB Output is correct
2 Correct 87 ms 15672 KB Output is correct
3 Correct 88 ms 14964 KB Output is correct
4 Correct 84 ms 15172 KB Output is correct
5 Correct 83 ms 15212 KB Output is correct
6 Correct 68 ms 14128 KB Output is correct
7 Correct 66 ms 14148 KB Output is correct
8 Correct 77 ms 14664 KB Output is correct
9 Correct 45 ms 5164 KB Output is correct
10 Correct 74 ms 14708 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 564 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 6 ms 1100 KB Output is correct
15 Correct 5 ms 1100 KB Output is correct
16 Correct 4 ms 1100 KB Output is correct
17 Correct 4 ms 844 KB Output is correct
18 Correct 4 ms 980 KB Output is correct
19 Correct 234 ms 31600 KB Output is correct
20 Correct 234 ms 31556 KB Output is correct
21 Correct 194 ms 30216 KB Output is correct
22 Correct 194 ms 30144 KB Output is correct
23 Correct 189 ms 30152 KB Output is correct
24 Correct 166 ms 27836 KB Output is correct
25 Correct 200 ms 28228 KB Output is correct
26 Correct 188 ms 28852 KB Output is correct
27 Correct 187 ms 28852 KB Output is correct
28 Correct 283 ms 29088 KB Output is correct
29 Correct 210 ms 29892 KB Output is correct
30 Correct 242 ms 30008 KB Output is correct
31 Correct 214 ms 30388 KB Output is correct
32 Correct 224 ms 30412 KB Output is correct
33 Correct 217 ms 30404 KB Output is correct
34 Correct 162 ms 28600 KB Output is correct
35 Correct 158 ms 28612 KB Output is correct
36 Correct 162 ms 28860 KB Output is correct
37 Correct 153 ms 29636 KB Output is correct
38 Correct 163 ms 29488 KB Output is correct
39 Correct 179 ms 31036 KB Output is correct
40 Correct 152 ms 22924 KB Output is correct
41 Correct 176 ms 30276 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 564 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 6 ms 1100 KB Output is correct
15 Correct 5 ms 1100 KB Output is correct
16 Correct 4 ms 1100 KB Output is correct
17 Correct 4 ms 844 KB Output is correct
18 Correct 4 ms 980 KB Output is correct
19 Correct 1435 ms 137604 KB Output is correct
20 Correct 1432 ms 135612 KB Output is correct
21 Correct 1479 ms 135624 KB Output is correct
22 Correct 1395 ms 135620 KB Output is correct
23 Correct 1293 ms 124752 KB Output is correct
24 Correct 100 ms 16332 KB Output is correct
25 Correct 87 ms 15672 KB Output is correct
26 Correct 88 ms 14964 KB Output is correct
27 Correct 84 ms 15172 KB Output is correct
28 Correct 83 ms 15212 KB Output is correct
29 Correct 68 ms 14128 KB Output is correct
30 Correct 66 ms 14148 KB Output is correct
31 Correct 77 ms 14664 KB Output is correct
32 Correct 45 ms 5164 KB Output is correct
33 Correct 74 ms 14708 KB Output is correct
34 Correct 234 ms 31600 KB Output is correct
35 Correct 234 ms 31556 KB Output is correct
36 Correct 194 ms 30216 KB Output is correct
37 Correct 194 ms 30144 KB Output is correct
38 Correct 189 ms 30152 KB Output is correct
39 Correct 166 ms 27836 KB Output is correct
40 Correct 200 ms 28228 KB Output is correct
41 Correct 188 ms 28852 KB Output is correct
42 Correct 187 ms 28852 KB Output is correct
43 Correct 283 ms 29088 KB Output is correct
44 Correct 210 ms 29892 KB Output is correct
45 Correct 242 ms 30008 KB Output is correct
46 Correct 214 ms 30388 KB Output is correct
47 Correct 224 ms 30412 KB Output is correct
48 Correct 217 ms 30404 KB Output is correct
49 Correct 162 ms 28600 KB Output is correct
50 Correct 158 ms 28612 KB Output is correct
51 Correct 162 ms 28860 KB Output is correct
52 Correct 153 ms 29636 KB Output is correct
53 Correct 163 ms 29488 KB Output is correct
54 Correct 179 ms 31036 KB Output is correct
55 Correct 152 ms 22924 KB Output is correct
56 Correct 176 ms 30276 KB Output is correct
57 Correct 1442 ms 137180 KB Output is correct
58 Correct 1428 ms 137228 KB Output is correct
59 Correct 1346 ms 133872 KB Output is correct
60 Correct 1377 ms 134208 KB Output is correct
61 Correct 1345 ms 134148 KB Output is correct
62 Correct 1397 ms 134224 KB Output is correct
63 Correct 904 ms 116976 KB Output is correct
64 Correct 881 ms 116924 KB Output is correct
65 Correct 1205 ms 123488 KB Output is correct
66 Correct 1209 ms 123388 KB Output is correct
67 Correct 1211 ms 123724 KB Output is correct
68 Correct 1274 ms 127324 KB Output is correct
69 Correct 1273 ms 127268 KB Output is correct
70 Correct 1261 ms 126516 KB Output is correct
71 Correct 1268 ms 126524 KB Output is correct
72 Correct 1270 ms 126504 KB Output is correct
73 Correct 825 ms 116604 KB Output is correct
74 Correct 854 ms 116400 KB Output is correct
75 Correct 818 ms 116524 KB Output is correct
76 Correct 818 ms 116248 KB Output is correct
77 Correct 821 ms 116520 KB Output is correct
78 Correct 1083 ms 124648 KB Output is correct
79 Correct 832 ms 80948 KB Output is correct
80 Correct 1052 ms 122464 KB Output is correct