제출 #401334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401334		NintsiChkhaidze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	2246 ms	129536 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];
deque <pair<int,int> > dq;
vector <pair<pair<int,int>,int> > v[N];

void Push(int node,int l,int r){
    if (add[node] == -1) return;
    if (l!=r){
        add[(node<<1)] = add[((node<<1)|1)] = add[node];
        int mid = (l+r)>>1;
        sgt[(node<<1)] = add[node]*(mid - l + 1) + pref[mid] - pref[l - 1];
        sgt[((node<<1)|1)] = add[node]*(r - mid) + pref[r] - pref[mid];
    }
    add[node]=-1;
}
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*(r - l + 1) + pref[r] - pref[l - 1];
        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);
    int n,q;
    cin>>n>>q;
    
    for (int i=1;i<=n;i++) 
        cin>>a[i],pref[i] = pref[i - 1] + a[i];
    
    for (int i=1;i<=4*N;i++) 
        add[i] = -1;
        
    for (int i=1;i<=q;i++){
        int l,r,k;
        cin>>l>>r>>k;
        v[l].pb({{r,k},i});
    }
    dq.push_back({2e9,n + 1});
    
    for (int i=n;i>=1;i--){
        if (i == n) dq.push_back({a[n],n});
        else{
            bool z=0;
            while(dq.back().f < a[i]) dq.pop_back(),z=1;
            if (z) upd(1,1,n,i + 1,dq.back().s - 1,a[i]);//,cout<<i+ 1<<" "<<dq.back().s - 1<<" "<<a[i]<<endl;
            dq.push_back({a[i],i});
        }
       // cout<<get(1,1,n,1,3)<< " + " <<get(1,1,n,1,6)<<endl;
        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);
            //cout<<x<<" "<<i<<" - "<<r<<endl;
            if (x > k) ans[ind] = 0;
            else ans[ind] = 1;
        }
    }
    
    for (int i=1;i<=q;i++) 
        cout<<ans[i]<<"\n";
}

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

sortbooks.cpp:43:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main (){
      |       ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:70: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]
   70 |         for (int j=0;j<v[i].size();j++){
      |                      ~^~~~~~~~~~~~
sortbooks.cpp:52:16: warning: iteration 4000019 invokes undefined behavior [-Waggressive-loop-optimizations]
   52 |         add[i] = -1;
      |         ~~~~~~~^~~~
sortbooks.cpp:51:19: note: within this loop
   51 |     for (int i=1;i<=4*N;i++)
      |                  ~^~~~~

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