Submission #886693

#	Time	Username	Problem	Language	Result	Execution time	Memory
886693		vjudge1	Doktor (COCI17_doktor)	C++17	70 / 100	151 ms	97620 KiB

doktor

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=5e5+100;
#else
    const int lim=2e3+100;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int int64_t
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

struct fenwick{
    int n;
    int tree[lim];
    fenwick(int n):n(n){
        memset(tree,0,sizeof(tree));
    }
    void update(int p){
        while(p<=n){
            tree[p]++;
            p+=p&-p;
        }
    }
    int query(int p){
        int res=0;
        while(p){
            res+=tree[p];
            p-=p&-p;
        }
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
};

inline void solve(){
    int n;
    cin>>n;
    int a[2*n+1];
    memset(a,0,sizeof(a));
    for(int i=2;i<=2*n;i+=2){
        cin>>a[i];
        a[i]*=2;
    }
    vector<int>need[2*n+1];
    fenwick all(2*n+1);
    for(int i=2;i<=2*n;i+=2){
        int mid=(a[i]+i)>>1;
        if(a[i]==i){
            all.update(i);
        }
        else need[mid].pb(abs(mid-a[i]));
    }
    int best=INT_MIN,l=a[2]/2,r=a[2]/2;
    for(int i=2;i<=2*n;i++){
        sort(need[i].begin(),need[i].end());
        for(int j=0;j<need[i].size();j++){
            int can=j+1-all.query(i-need[i][j],i+need[i][j]);
            if(i==a[i])a[i]++;
            if(best<can){
                l=a[i-need[i][j]]/2;
                r=a[i+need[i][j]]/2;
                best=can;
            }
        }
    }
    cout<<l<<" "<<r<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen("grass.in","r",stdin);
    //freopen("grass.out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

doktor.cpp: In function 'void solve()':
doktor.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j=0;j<need[i].size();j++){
      |                     ~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10