Submission #600726

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600726	2022-07-21T07:29:57 Z	장태환(#8468)	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	409 ms	324 KB

arranging_tickets

#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;
    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];
        if(stree[1]>b)
        {
            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	389 ms	212 KB	Output is correct
2	Correct	409 ms	312 KB	Output is correct
3	Correct	354 ms	312 KB	Output is correct
4	Correct	371 ms	212 KB	Output is correct
5	Correct	343 ms	320 KB	Output is correct
6	Correct	354 ms	320 KB	Output is correct
7	Correct	370 ms	312 KB	Output is correct
8	Correct	397 ms	316 KB	Output is correct
9	Correct	384 ms	324 KB	Output is correct
10	Correct	382 ms	212 KB	Output is correct
11	Correct	351 ms	312 KB	Output is correct
12	Correct	408 ms	316 KB	Output is correct
13	Correct	357 ms	312 KB	Output is correct
14	Incorrect	384 ms	312 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	389 ms	212 KB	Output is correct
2	Correct	409 ms	312 KB	Output is correct
3	Correct	354 ms	312 KB	Output is correct
4	Correct	371 ms	212 KB	Output is correct
5	Correct	343 ms	320 KB	Output is correct
6	Correct	354 ms	320 KB	Output is correct
7	Correct	370 ms	312 KB	Output is correct
8	Correct	397 ms	316 KB	Output is correct
9	Correct	384 ms	324 KB	Output is correct
10	Correct	382 ms	212 KB	Output is correct
11	Correct	351 ms	312 KB	Output is correct
12	Correct	408 ms	316 KB	Output is correct
13	Correct	357 ms	312 KB	Output is correct
14	Incorrect	384 ms	312 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	389 ms	212 KB	Output is correct
2	Correct	409 ms	312 KB	Output is correct
3	Correct	354 ms	312 KB	Output is correct
4	Correct	371 ms	212 KB	Output is correct
5	Correct	343 ms	320 KB	Output is correct
6	Correct	354 ms	320 KB	Output is correct
7	Correct	370 ms	312 KB	Output is correct
8	Correct	397 ms	316 KB	Output is correct
9	Correct	384 ms	324 KB	Output is correct
10	Correct	382 ms	212 KB	Output is correct
11	Correct	351 ms	312 KB	Output is correct
12	Correct	408 ms	316 KB	Output is correct
13	Correct	357 ms	312 KB	Output is correct
14	Incorrect	384 ms	312 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	389 ms	212 KB	Output is correct
2	Correct	409 ms	312 KB	Output is correct
3	Correct	354 ms	312 KB	Output is correct
4	Correct	371 ms	212 KB	Output is correct
5	Correct	343 ms	320 KB	Output is correct
6	Correct	354 ms	320 KB	Output is correct
7	Correct	370 ms	312 KB	Output is correct
8	Correct	397 ms	316 KB	Output is correct
9	Correct	384 ms	324 KB	Output is correct
10	Correct	382 ms	212 KB	Output is correct
11	Correct	351 ms	312 KB	Output is correct
12	Correct	408 ms	316 KB	Output is correct
13	Correct	357 ms	312 KB	Output is correct
14	Incorrect	384 ms	312 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	389 ms	212 KB	Output is correct
2	Correct	409 ms	312 KB	Output is correct
3	Correct	354 ms	312 KB	Output is correct
4	Correct	371 ms	212 KB	Output is correct
5	Correct	343 ms	320 KB	Output is correct
6	Correct	354 ms	320 KB	Output is correct
7	Correct	370 ms	312 KB	Output is correct
8	Correct	397 ms	316 KB	Output is correct
9	Correct	384 ms	324 KB	Output is correct
10	Correct	382 ms	212 KB	Output is correct
11	Correct	351 ms	312 KB	Output is correct
12	Correct	408 ms	316 KB	Output is correct
13	Correct	357 ms	312 KB	Output is correct
14	Incorrect	384 ms	312 KB	Output isn't correct
15	Halted	0 ms	0 KB	-