oj.uz

Submission #133599

# Submission time Handle Problem Language Result Execution time Memory
133599 2019-07-21T06:07:50 Z forelax Kralj (COCI16_kralj) C++14
140 / 140
 1446 ms 72752 KB 
#include<bits/stdc++.h>
using namespace std;
int n,rez=0;
vector<int> a,p,v;
inline void solve(vector<int>& A,vector<vector<int> >& B){
    int N=A.size();
    set<int> s;
    for(int i = 0 ; i < N ; i ++){
        for(int j = 0 ; j < B[i].size() ; j ++)
            s.insert(v[B[i][j]]);
        if(s.upper_bound(A[i])==s.end()){
            s.erase(s.begin());
        }else{
            s.erase(s.upper_bound(A[i]));
            rez++;
        }
    }
}
int main(){
    cin>>n;
    a.resize(n);
    p.resize(n);
    v.resize(n);
    vector<int> hs(2*n);
    vector<vector<int> > cmp(n);
    for(int i = 0 ; i < n ; i ++){
        cin>>a[i];
        a[i]--;
        hs[a[i]]++;
        hs[n+a[i]]++;
        cmp[a[i]].push_back(i);
    }
    for(int i = 0 ; i < n ; i ++)
        cin>>p[i];
    for(int i = 0 ; i < n ; i ++)
        cin>>v[i];
    int ml=0;
    int ps=-1;
    for(int i = 0 ; i < hs.size() ; i ++){
        if(hs[i]){
            int j=i;
            int c=hs[i];
            while(c){
                c--;
                if(c&&j+1<hs.size()){
                    j++;
                    c+=hs[j];
                }
            }
            int l=j-i+1;
            if(l>ml){
                ml=l;
                ps=i;
            }
            i=j;
        }
    }
    for(int i = ps ; i < ps+n ; i ++){
        if(hs[i]){
            int j=i;
            int c=hs[i];
            vector<int> fv;
            vector<vector<int> > g;
            while(c){
                fv.push_back(p[j%n]);
                g.push_back(cmp[j%n]);
                c--;
                if(c&&j+1<hs.size()){
                    j++;
                    c+=hs[j];
                }
            }
            solve(fv,g);
            i=j;
        }
    }
    cout<<rez;
}

Compilation message

kralj.cpp: In function 'void solve(std::vector<int>&, std::vector<std::vector<int> >&)':
kralj.cpp:9:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0 ; j < B[i].size() ; j ++)
                         ~~^~~~~~~~~~~~~
kralj.cpp: In function 'int main()':
kralj.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < hs.size() ; i ++){
                     ~~^~~~~~~~~~~
kralj.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(c&&j+1<hs.size()){
                       ~~~^~~~~~~~~~
kralj.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(c&&j+1<hs.size()){
                       ~~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1446 ms 59340 KB Output is correct
2 Correct 1122 ms 57420 KB Output is correct
3 Correct 1408 ms 71436 KB Output is correct
4 Correct 1414 ms 72752 KB Output is correct
5 Correct 1247 ms 50304 KB Output is correct
6 Correct 1137 ms 50056 KB Output is correct
7 Correct 1375 ms 58260 KB Output is correct
8 Correct 1182 ms 54164 KB Output is correct
9 Correct 1439 ms 61128 KB Output is correct
10 Correct 1277 ms 53852 KB Output is correct