Submission #164806

#	Time	Username	Problem	Language	Result	Execution time	Memory
164806		mosiashvililuka	Money (IZhO17_money)	C++14	0 / 100	49 ms	47452 KiB

money

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,pas,f[1000009],read2[1000009],read[1000009],p[1000009],pi,mi=1000003,dp[1000009],fen[1000009];
vector <int> v[2000009];
vector <int>::iterator it;
void upd(int q, int w){
    while(q<=1000000){
        fen[q]+=w;
        q=q+(q&(-q));
    }
}
int readd(int q){
    if(q<=0) return 0;
    int jm=0;
    while(q>0){
        jm+=fen[q];
        q=q-(q&(-q));
    }
    return jm;
}
int main(){
    scanf("%d",&a);
    for(b=1; b<=a; b++){
        scanf("%d",&p[b]);
    }
    for(b=1; b<=a; b++){
        if(p[b]==p[b-1]) continue;
        pi++;
        f[pi]=p[b];
        upd(p[b],1);
        read[b]=readd(p[b]);
        read2[b]=readd(p[b]-1);
    }
    a=pi;
    dp[0]=1;
    for(b=1; b<=a; b++){
        if(f[b]>=f[b-1]) dp[b]=dp[b-1]; else dp[b]=b;
    }
//    for(b=1; b<=1000000; b++) read[b]+=read[b-1];
/*    for(b=1; b<=a; b++) cout<<read[b]<<" ";
    return 0;*/
    for(b=1; b<=a; b++){
        v[read[b]-b+mi].push_back(b);
    }
    b=a;
    while(b>0){
        //cout<<b<<endl;
        pas++;
        it=lower_bound(v[read2[b]-b+1+mi].begin(),v[read2[b]-b+1+mi].end(),dp[b]);
        if(it==v[read2[b]-b+1+mi].end()||(*it)>=b){
            b=b-1;
            continue;
        }
        b=(*it)-1;
    }
    cout<<pas;
    return 0;
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a);
     ~~~~~^~~~~~~~~
money.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[b]);
         ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55