oj.uz

Submission #886694

# Submission time Handle Problem Language Result Execution time Memory
886694 2023-12-12T16:44:27 Z vjudge1 Doktor (COCI17_doktor) C++17
100 / 100
 194 ms 50768 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=10e5+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+5];
    fenwick all(2*n+5);
    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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8024 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8280 KB Output is correct
2 Correct 5 ms 8280 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 5 ms 8280 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9048 KB Output is correct
2 Correct 66 ms 32548 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15960 KB Output is correct
2 Correct 27 ms 15860 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 50768 KB Output is correct
2 Correct 113 ms 48716 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 33096 KB Output is correct
2 Correct 61 ms 41668 KB Output is correct