제출 #401341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401341		NintsiChkhaidze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2003 ms	173224 KiB

sortbooks

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define int long long
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 1000005;
int a[N],sgt[4*N],ans[N],add[4*N],pref[4*N],t[4*N],n,q;
deque <pair<int,int> > dq;
vector <pair<pair<int,int>,int> > v[N];
 
void Build(int node,int l,int r){
    if (l == r) {t[node] = l; return;}
    Build(left),Build(right);
    int x = t[(node<<1)],y = t[((node<<1)|1)];
    if (a[x] > a[y]) t[node] = x;
    else t[node] = y;
}
int GET(int node,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return t[node];
    int x = GET(left,L,R),y = GET(right,L,R);
    if (a[x] > a[y]) return x;
    return y;
}
void Push(int node,int l,int r){
    if (add[node] == 0) return;
    if (l!=r){
        add[(node<<1)] = add[((node<<1)|1)] = add[node];
        int mid = ((l+r)>>1);
        sgt[(node<<1)] = add[node] + t[(node<<1)];
        sgt[((node<<1)|1)] = add[node] + t[((node<<1)|1)];
    }
    add[node]=0;
}
void upd(int node,int l,int r,int L,int R,int val){
    if (r < L || R < l) return ;
    if (L <= l && r <= R) {
        sgt[node] = val + t[node];
        add[node] = val;
        return;
    }
    Push(node,l,r);
    upd(left,L,R,val),upd(right,L,R,val);
    sgt[node] = max(sgt[(node<<1)],sgt[((node<<1)|1)]);
}
ll get(int node,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return sgt[node];
    Push(node,l,r);
    ll x = get(left,L,R),y=get(right,L,R);
    return max(x,y);
}
main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    cin>>n>>q;
    
    for (int i=1;i<=n;i++) 
        cin>>a[i];
        
    a[0] = 0;
    Build(1,1,n);
    
    for (int i=1;i<=4*N;i++)
        t[i] = a[t[i]];
        
    for (int i=1;i<=q;i++){
        int l,r,k;
        cin>>l>>r>>k;
        v[l].pb({{r,k},i});
    }
    dq.push_back({5e9,n + 1});
    
    for (int i=n;i>=1;i--){
        if (i == n) dq.push_back({a[n],n});
        else{
            while(dq.back().f < a[i]) dq.pop_back();
            if (i + 1 <= dq.back().s - 1)
                upd(1,1,n,i + 1,dq.back().s - 1,a[i]);
            
            dq.push_back({a[i],i});
        }
        
        for (int j=0;j<v[i].size();j++){
            int r = v[i][j].f.f,k = v[i][j].f.s,ind = v[i][j].s;
            ll x = get(1,1,n,i,r);
            if (x > k) ans[ind] = 0;
            else ans[ind] = 1;
        }
    }
    
    for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'void Push(long long int, long long int, long long int)':
sortbooks.cpp:33:13: warning: unused variable 'mid' [-Wunused-variable]
   33 |         int mid = ((l+r)>>1);
      |             ^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:57:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main (){
      |       ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:87:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int j=0;j<v[i].size();j++){
      |                      ~^~~~~~~~~~~~
sortbooks.cpp:68:21: warning: iteration 4000019 invokes undefined behavior [-Waggressive-loop-optimizations]
   68 |         t[i] = a[t[i]];
      |                  ~~~^
sortbooks.cpp:67:19: note: within this loop
   67 |     for (int i=1;i<=4*N;i++)
      |                  ~^~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23