oj.uz

Submission #600737

# Submission time Handle Problem Language Result Execution time Memory
600737 2022-07-21T07:32:14 Z 장태환(#8468) Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 407 ms 312 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;
    for(i=0;i<M;i++)
    {
        int a;
        cin >>arr[i][0]>>arr[i][1]>>a;
        if(arr[i][0]>arr[i][1])
            swap(arr[i][0],arr[i][1]);
        arr[i][1]--;
        upd(arr[i][0],arr[i][1],1);
    }
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> d(0,M-1);
    int T=1000000;
    int mi=1<<30;
    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,stree[1]);
        if(stree[1]>b)
        {
            if(d(gen)==0)
                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];
        }
    }
    cout <<stree[1];

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 304 KB Output is correct
2 Correct 407 ms 308 KB Output is correct
3 Incorrect 354 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 304 KB Output is correct
2 Correct 407 ms 308 KB Output is correct
3 Incorrect 354 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 304 KB Output is correct
2 Correct 407 ms 308 KB Output is correct
3 Incorrect 354 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 304 KB Output is correct
2 Correct 407 ms 308 KB Output is correct
3 Incorrect 354 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 304 KB Output is correct
2 Correct 407 ms 308 KB Output is correct
3 Incorrect 354 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -