oj.uz

Submission #600744

# Submission time Handle Problem Language Result Execution time Memory
600744 2022-07-21T07:34:31 Z 장태환(#8468) Arranging Tickets (JOI17_arranging_tickets) C++17
45 / 100
 1469 ms 432 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,b);
        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 <<mi;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 312 KB Output is correct
2 Correct 440 ms 316 KB Output is correct
3 Correct 413 ms 316 KB Output is correct
4 Correct 409 ms 312 KB Output is correct
5 Correct 401 ms 312 KB Output is correct
6 Correct 379 ms 312 KB Output is correct
7 Correct 429 ms 312 KB Output is correct
8 Correct 398 ms 312 KB Output is correct
9 Correct 413 ms 316 KB Output is correct
10 Correct 416 ms 312 KB Output is correct
11 Correct 381 ms 308 KB Output is correct
12 Correct 406 ms 316 KB Output is correct
13 Correct 511 ms 316 KB Output is correct
14 Correct 606 ms 312 KB Output is correct
15 Correct 446 ms 316 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 312 KB Output is correct
2 Correct 440 ms 316 KB Output is correct
3 Correct 413 ms 316 KB Output is correct
4 Correct 409 ms 312 KB Output is correct
5 Correct 401 ms 312 KB Output is correct
6 Correct 379 ms 312 KB Output is correct
7 Correct 429 ms 312 KB Output is correct
8 Correct 398 ms 312 KB Output is correct
9 Correct 413 ms 316 KB Output is correct
10 Correct 416 ms 312 KB Output is correct
11 Correct 381 ms 308 KB Output is correct
12 Correct 406 ms 316 KB Output is correct
13 Correct 511 ms 316 KB Output is correct
14 Correct 606 ms 312 KB Output is correct
15 Correct 446 ms 316 KB Output is correct
16 Correct 916 ms 340 KB Output is correct
17 Correct 1223 ms 324 KB Output is correct
18 Correct 949 ms 340 KB Output is correct
19 Correct 892 ms 340 KB Output is correct
20 Correct 1012 ms 340 KB Output is correct
21 Correct 942 ms 324 KB Output is correct
22 Correct 903 ms 324 KB Output is correct
23 Correct 968 ms 324 KB Output is correct
24 Correct 912 ms 340 KB Output is correct
25 Correct 845 ms 340 KB Output is correct
26 Correct 872 ms 340 KB Output is correct
27 Correct 997 ms 340 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 312 KB Output is correct
2 Correct 440 ms 316 KB Output is correct
3 Correct 413 ms 316 KB Output is correct
4 Correct 409 ms 312 KB Output is correct
5 Correct 401 ms 312 KB Output is correct
6 Correct 379 ms 312 KB Output is correct
7 Correct 429 ms 312 KB Output is correct
8 Correct 398 ms 312 KB Output is correct
9 Correct 413 ms 316 KB Output is correct
10 Correct 416 ms 312 KB Output is correct
11 Correct 381 ms 308 KB Output is correct
12 Correct 406 ms 316 KB Output is correct
13 Correct 511 ms 316 KB Output is correct
14 Correct 606 ms 312 KB Output is correct
15 Correct 446 ms 316 KB Output is correct
16 Correct 916 ms 340 KB Output is correct
17 Correct 1223 ms 324 KB Output is correct
18 Correct 949 ms 340 KB Output is correct
19 Correct 892 ms 340 KB Output is correct
20 Correct 1012 ms 340 KB Output is correct
21 Correct 942 ms 324 KB Output is correct
22 Correct 903 ms 324 KB Output is correct
23 Correct 968 ms 324 KB Output is correct
24 Correct 912 ms 340 KB Output is correct
25 Correct 845 ms 340 KB Output is correct
26 Correct 872 ms 340 KB Output is correct
27 Correct 997 ms 340 KB Output is correct
28 Correct 1466 ms 432 KB Output is correct
29 Correct 1353 ms 432 KB Output is correct
30 Correct 1336 ms 428 KB Output is correct
31 Correct 1412 ms 428 KB Output is correct
32 Correct 1469 ms 428 KB Output is correct
33 Incorrect 1367 ms 432 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 312 KB Output is correct
2 Correct 440 ms 316 KB Output is correct
3 Correct 413 ms 316 KB Output is correct
4 Correct 409 ms 312 KB Output is correct
5 Correct 401 ms 312 KB Output is correct
6 Correct 379 ms 312 KB Output is correct
7 Correct 429 ms 312 KB Output is correct
8 Correct 398 ms 312 KB Output is correct
9 Correct 413 ms 316 KB Output is correct
10 Correct 416 ms 312 KB Output is correct
11 Correct 381 ms 308 KB Output is correct
12 Correct 406 ms 316 KB Output is correct
13 Correct 511 ms 316 KB Output is correct
14 Correct 606 ms 312 KB Output is correct
15 Correct 446 ms 316 KB Output is correct
16 Correct 916 ms 340 KB Output is correct
17 Correct 1223 ms 324 KB Output is correct
18 Correct 949 ms 340 KB Output is correct
19 Correct 892 ms 340 KB Output is correct
20 Correct 1012 ms 340 KB Output is correct
21 Correct 942 ms 324 KB Output is correct
22 Correct 903 ms 324 KB Output is correct
23 Correct 968 ms 324 KB Output is correct
24 Correct 912 ms 340 KB Output is correct
25 Correct 845 ms 340 KB Output is correct
26 Correct 872 ms 340 KB Output is correct
27 Correct 997 ms 340 KB Output is correct
28 Correct 1466 ms 432 KB Output is correct
29 Correct 1353 ms 432 KB Output is correct
30 Correct 1336 ms 428 KB Output is correct
31 Correct 1412 ms 428 KB Output is correct
32 Correct 1469 ms 428 KB Output is correct
33 Incorrect 1367 ms 432 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 312 KB Output is correct
2 Correct 440 ms 316 KB Output is correct
3 Correct 413 ms 316 KB Output is correct
4 Correct 409 ms 312 KB Output is correct
5 Correct 401 ms 312 KB Output is correct
6 Correct 379 ms 312 KB Output is correct
7 Correct 429 ms 312 KB Output is correct
8 Correct 398 ms 312 KB Output is correct
9 Correct 413 ms 316 KB Output is correct
10 Correct 416 ms 312 KB Output is correct
11 Correct 381 ms 308 KB Output is correct
12 Correct 406 ms 316 KB Output is correct
13 Correct 511 ms 316 KB Output is correct
14 Correct 606 ms 312 KB Output is correct
15 Correct 446 ms 316 KB Output is correct
16 Correct 916 ms 340 KB Output is correct
17 Correct 1223 ms 324 KB Output is correct
18 Correct 949 ms 340 KB Output is correct
19 Correct 892 ms 340 KB Output is correct
20 Correct 1012 ms 340 KB Output is correct
21 Correct 942 ms 324 KB Output is correct
22 Correct 903 ms 324 KB Output is correct
23 Correct 968 ms 324 KB Output is correct
24 Correct 912 ms 340 KB Output is correct
25 Correct 845 ms 340 KB Output is correct
26 Correct 872 ms 340 KB Output is correct
27 Correct 997 ms 340 KB Output is correct
28 Correct 1466 ms 432 KB Output is correct
29 Correct 1353 ms 432 KB Output is correct
30 Correct 1336 ms 428 KB Output is correct
31 Correct 1412 ms 428 KB Output is correct
32 Correct 1469 ms 428 KB Output is correct
33 Incorrect 1367 ms 432 KB Output isn't correct
34 Halted 0 ms 0 KB -