oj.uz

Submission #299543

# Submission time Handle Problem Language Result Execution time Memory
299543 2020-09-15T07:14:28 Z gs18115 Archery (IOI09_archery) C++14
57 / 100
 932 ms 10676 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
    struct node
    {
        int sum;
        int mxl;
        node(int v=0):sum(v),mxl(v){}
        node(int sum,int mxl):sum(sum),mxl(mxl){}
        node operator+(const node&x)
        {
            return node(sum+x.sum,max(mxl,sum+x.mxl));
        }
    }t[mx*4];
    void init(int n,int s,int e,vector<int>&v)
    {
        if(s==e)
        {
            t[n]=node(v[s]);
            return;
        }
        int m=s+(e-s)/2;
        init(n*2,s,m,v);
        init(n*2+1,m+1,e,v);
        t[n]=t[n*2]+t[n*2+1];
        return;
    }
    int query(int n,int s,int e,int S,int E,int lft)
    {
        if(s>E||S>e)
            return 0;
        if(S<=s&&e<=E&&t[n].mxl+lft<0)
            return t[n].sum+lft;
        if(s==e)
            return s;
        int m=s+(e-s)/2;
        int lf=query(n*2,s,m,S,E,lft);
        if(lf>0)
            return lf;
        return query(n*2+1,m+1,e,S,E,lf);
    }
}st;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,r;
    cin>>n>>r;
    r=(r-n*2)%n+n*2;
    int s;
    cin>>s;
    vector<int>v(n*2-1);
    for(int&t:v)
    {
        cin>>t;
        t=t>s?1:0;
    }
    vector<int>memo(n+1,inf);
    auto getpos=[&](int start)->int
    {
        if(s==1)
            return 1;
        if(memo[start]!=inf)
            return memo[start];
        vector<int>cnt(n+1,0);
        for(int i=1;i<start;i++)
            cnt[i]=v[i*2-2]+v[i*2-1]-1;
        cnt[start]=v[start*2-2]-1;
        for(int i=start;i++<n;)
            cnt[i]=v[i*2-3]+v[i*2-2]-1;
        vector<int>tm(n+1,inf);
        for(int i=0;i++<n;)
        {
            if(cnt[i]<(i==start?1:2))
            {
                tm[1]=i-1;
                break;
            }
        }
        st.init(1,1,n,cnt);
        for(int i=1;i++<n;)
        {
            int fi=st.query(1,1,n,i,n,0);
            if(fi>0)
                tm[i]=fi-i;
            else
            {
                int se=st.query(1,1,n,1,i-1,fi+1);
                if(se>0)
                {
                    tm[i]=n-i+se;
                    if(se<=tm[1])
                        tm[i]++;
                }
            }
        }
        int cur=start,cc=start;
        for(int t=0;t<r;t++)
        {
            if(t>=tm[cc])
                cur--,cc--;
            if(cc==0)
                cc=n;
        }
        return memo[start]=cur;
    };
    {
        int pos=getpos(n);
        while((pos-1)%n!=0)
            pos--;
        int s=1,e=n;
        while(s<e)
        {
            int m=s+(e-s)/2;
            if(getpos(m)<pos)
                s=m+1;
            else
                e=m;
        }
        pos=getpos(s);
        e=n;
        for(int i=s;i++<n;)
            if(memo[i]>pos)
                e=min(e,i-1);
        for(int i=s;i++<n;)
            if(memo[i]==pos)
                s=i;
        while(s<e)
        {
            int m=s+(e-s+1)/2;
            if(getpos(m)==pos)
                s=m;
            else
                e=m-1;
        }
        cout<<s<<endl;
    }
    return 0;
}

Subtask #1
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6528 KB Output isn't correct
2 Incorrect 5 ms 6656 KB Output isn't correct
3 Correct 5 ms 6528 KB Output is correct
4 Incorrect 9 ms 6784 KB Output isn't correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 5 ms 6632 KB Output is correct

Subtask #2
54.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6560 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Incorrect 7 ms 6656 KB Output isn't correct
4 Incorrect 42 ms 6912 KB Output isn't correct
5 Correct 641 ms 9984 KB Output is correct
6 Correct 5 ms 6656 KB Output is correct
7 Incorrect 7 ms 6656 KB Output isn't correct
8 Incorrect 38 ms 6912 KB Output isn't correct
9 Correct 67 ms 7060 KB Output is correct
10 Incorrect 7 ms 6656 KB Output isn't correct
11 Incorrect 57 ms 7064 KB Output isn't correct
12 Incorrect 10 ms 6656 KB Output isn't correct
13 Incorrect 474 ms 9344 KB Output isn't correct
14 Incorrect 14 ms 6656 KB Output isn't correct
15 Incorrect 100 ms 7312 KB Output isn't correct
16 Incorrect 5 ms 6528 KB Output isn't correct
17 Incorrect 7 ms 6656 KB Output isn't correct
18 Incorrect 9 ms 6656 KB Output isn't correct
19 Correct 12 ms 6784 KB Output is correct
20 Correct 17 ms 6656 KB Output is correct
21 Incorrect 57 ms 7072 KB Output isn't correct
22 Correct 108 ms 7376 KB Output is correct
23 Incorrect 686 ms 10396 KB Output isn't correct
24 Incorrect 5 ms 6656 KB Output isn't correct
25 Incorrect 6 ms 6656 KB Output isn't correct
26 Correct 24 ms 6656 KB Output is correct
27 Incorrect 68 ms 7080 KB Output isn't correct
28 Incorrect 508 ms 9144 KB Output isn't correct
29 Correct 8 ms 6656 KB Output is correct
30 Correct 20 ms 6656 KB Output is correct
31 Correct 69 ms 7056 KB Output is correct
32 Correct 816 ms 10380 KB Output is correct
33 Correct 5 ms 6528 KB Output is correct
34 Correct 5 ms 6656 KB Output is correct
35 Correct 9 ms 6656 KB Output is correct
36 Correct 11 ms 6656 KB Output is correct
37 Incorrect 54 ms 6984 KB Output isn't correct
38 Correct 83 ms 7136 KB Output is correct
39 Correct 5 ms 6560 KB Output is correct
40 Correct 6 ms 6656 KB Output is correct
41 Correct 9 ms 6656 KB Output is correct
42 Correct 10 ms 6656 KB Output is correct
43 Correct 17 ms 6656 KB Output is correct
44 Correct 34 ms 6784 KB Output is correct
45 Correct 78 ms 7056 KB Output is correct
46 Correct 68 ms 7072 KB Output is correct
47 Correct 932 ms 10676 KB Output is correct