Submission #133599

#	Time	Username	Problem	Language	Result	Execution time	Memory
133599		forelax	Kralj (COCI16_kralj)	C++14	140 / 140	1446 ms	72752 KiB

kralj

#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 (stderr)

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 / 140