oj.uz

Submission #164806

# Submission time Handle Problem Language Result Execution time Memory
164806 2019-11-23T13:57:27 Z mosiashvililuka Money (IZhO17_money) C++14
0 / 100
 49 ms 47452 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47352 KB Output is correct
2 Correct 49 ms 47356 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47356 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47452 KB Output is correct
7 Incorrect 48 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47352 KB Output is correct
2 Correct 49 ms 47356 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47356 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47452 KB Output is correct
7 Incorrect 48 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47352 KB Output is correct
2 Correct 49 ms 47356 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47356 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47452 KB Output is correct
7 Incorrect 48 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47352 KB Output is correct
2 Correct 49 ms 47356 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47356 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47452 KB Output is correct
7 Incorrect 48 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -