oj.uz

Submission #600792

# Submission time Handle Problem Language Result Execution time Memory
600792 2022-07-21T07:50:46 Z 장태환(#8468) Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 1000 ms 8600 KB 
#include <bits/stdc++.h>
using namespace std;
int stree[1<<20];
int lazy[1<<20];
int treeN;
void ul(int n)
{
    stree[n]+=lazy[n];
    if(n<treeN)
    {
        lazy[n*2]+=lazy[n];
        lazy[n*2+1]+=lazy[n];
    }
    lazy[n]=0;
}
void upd(int qs,int qe,int p,int s=0,int e=treeN-1,int i=1)
{
    ul(i);
    if(s>qe||qs>e)
    return;
    if(qs<=s&&e<=qe)
    {
        lazy[i]+=p;
        ul(i);
        return;
    }
    upd(qs,qe,p,s,(s+e)/2,i*2);
    upd(qs,qe,p,(s+e)/2+1,e,i*2+1);
    stree[i]=max(stree[i*2],stree[i*2+1]);
}
int arr[100100][2];
bool v[100100];
int main()
{
    int N,M;
    cin >>N>>M;
    for(treeN=1;treeN<N;treeN*=2);
    int i;
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> d(0,M-1);
    int RT=10;
    int mi=1<<30;
    while(RT--)
    {
        memset(stree,0,sizeof(stree));
        memset(lazy,0,sizeof(lazy));
        memset(v,0,sizeof(v));
        for(i=0;i<M;i++)
    {
        int a;
        if(RT==99)
            cin >>arr[i][0]>>arr[i][1]>>a;
        if(RT==99&&arr[i][0]>arr[i][1])
            swap(arr[i][0],arr[i][1]);
        if(RT==99)
            arr[i][1]--;
        upd(arr[i][0],arr[i][1],1);
        if(d(gen)%2)
        {
            v[i]=1;
            upd(arr[i][0],arr[i][1],-2);
            upd(0,N-1,1);
        }
    }

    int T=300000;

    int c=0;
    while(T--)
    {
        int a=d(gen);
        int b=stree[1];

        if(v[a])
        {
            upd(arr[a][0],arr[a][1],2);
            upd(0,N-1,-1);
        }
        else
        {
            upd(arr[a][0],arr[a][1],-2);
            upd(0,N-1,1);
        }
        v[a]=1-v[a];
        mi=min(mi,b);
        if(stree[1]>b)
        {
            c++;
            if(d(gen)<=c/M)
                continue;
            if(v[a])
            {
                upd(arr[a][0],arr[a][1],2);
                upd(0,N-1,-1);
            }
            else
            {
                upd(arr[a][0],arr[a][1],-2);
                upd(0,N-1,1);
            }
            v[a]=1-v[a];
            }
            else
            {
                c=0;
            }
        }

    }
    cout <<mi;

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1000 ms 8600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1000 ms 8600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1000 ms 8600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1000 ms 8600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1000 ms 8600 KB Output isn't correct
2 Halted 0 ms 0 KB -