oj.uz

Submission #600788

# Submission time Handle Problem Language Result Execution time Memory
600788 2022-07-21T07:49:10 Z 장태환(#8468) Arranging Tickets (JOI17_arranging_tickets) C++17
45 / 100
 4932 ms 8628 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=100;
    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=30000;

    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 8596 KB Output is correct
2 Correct 1299 ms 8596 KB Output is correct
3 Correct 1251 ms 8592 KB Output is correct
4 Correct 1503 ms 8596 KB Output is correct
5 Correct 1413 ms 8588 KB Output is correct
6 Correct 1443 ms 8592 KB Output is correct
7 Correct 1343 ms 8592 KB Output is correct
8 Correct 1297 ms 8532 KB Output is correct
9 Correct 1290 ms 8592 KB Output is correct
10 Correct 1389 ms 8592 KB Output is correct
11 Correct 1451 ms 8596 KB Output is correct
12 Correct 1361 ms 8592 KB Output is correct
13 Correct 1344 ms 8600 KB Output is correct
14 Correct 1396 ms 8600 KB Output is correct
15 Correct 1238 ms 8588 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 8596 KB Output is correct
2 Correct 1299 ms 8596 KB Output is correct
3 Correct 1251 ms 8592 KB Output is correct
4 Correct 1503 ms 8596 KB Output is correct
5 Correct 1413 ms 8588 KB Output is correct
6 Correct 1443 ms 8592 KB Output is correct
7 Correct 1343 ms 8592 KB Output is correct
8 Correct 1297 ms 8532 KB Output is correct
9 Correct 1290 ms 8592 KB Output is correct
10 Correct 1389 ms 8592 KB Output is correct
11 Correct 1451 ms 8596 KB Output is correct
12 Correct 1361 ms 8592 KB Output is correct
13 Correct 1344 ms 8600 KB Output is correct
14 Correct 1396 ms 8600 KB Output is correct
15 Correct 1238 ms 8588 KB Output is correct
16 Correct 2950 ms 8600 KB Output is correct
17 Correct 2822 ms 8604 KB Output is correct
18 Correct 3054 ms 8596 KB Output is correct
19 Correct 2670 ms 8596 KB Output is correct
20 Correct 2903 ms 8596 KB Output is correct
21 Correct 2699 ms 8596 KB Output is correct
22 Correct 3067 ms 8600 KB Output is correct
23 Correct 2731 ms 8600 KB Output is correct
24 Correct 3037 ms 8596 KB Output is correct
25 Correct 2669 ms 8596 KB Output is correct
26 Correct 2993 ms 8596 KB Output is correct
27 Correct 3136 ms 8604 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 8596 KB Output is correct
2 Correct 1299 ms 8596 KB Output is correct
3 Correct 1251 ms 8592 KB Output is correct
4 Correct 1503 ms 8596 KB Output is correct
5 Correct 1413 ms 8588 KB Output is correct
6 Correct 1443 ms 8592 KB Output is correct
7 Correct 1343 ms 8592 KB Output is correct
8 Correct 1297 ms 8532 KB Output is correct
9 Correct 1290 ms 8592 KB Output is correct
10 Correct 1389 ms 8592 KB Output is correct
11 Correct 1451 ms 8596 KB Output is correct
12 Correct 1361 ms 8592 KB Output is correct
13 Correct 1344 ms 8600 KB Output is correct
14 Correct 1396 ms 8600 KB Output is correct
15 Correct 1238 ms 8588 KB Output is correct
16 Correct 2950 ms 8600 KB Output is correct
17 Correct 2822 ms 8604 KB Output is correct
18 Correct 3054 ms 8596 KB Output is correct
19 Correct 2670 ms 8596 KB Output is correct
20 Correct 2903 ms 8596 KB Output is correct
21 Correct 2699 ms 8596 KB Output is correct
22 Correct 3067 ms 8600 KB Output is correct
23 Correct 2731 ms 8600 KB Output is correct
24 Correct 3037 ms 8596 KB Output is correct
25 Correct 2669 ms 8596 KB Output is correct
26 Correct 2993 ms 8596 KB Output is correct
27 Correct 3136 ms 8604 KB Output is correct
28 Correct 4932 ms 8616 KB Output is correct
29 Correct 4739 ms 8628 KB Output is correct
30 Correct 4208 ms 8620 KB Output is correct
31 Incorrect 4003 ms 8612 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 8596 KB Output is correct
2 Correct 1299 ms 8596 KB Output is correct
3 Correct 1251 ms 8592 KB Output is correct
4 Correct 1503 ms 8596 KB Output is correct
5 Correct 1413 ms 8588 KB Output is correct
6 Correct 1443 ms 8592 KB Output is correct
7 Correct 1343 ms 8592 KB Output is correct
8 Correct 1297 ms 8532 KB Output is correct
9 Correct 1290 ms 8592 KB Output is correct
10 Correct 1389 ms 8592 KB Output is correct
11 Correct 1451 ms 8596 KB Output is correct
12 Correct 1361 ms 8592 KB Output is correct
13 Correct 1344 ms 8600 KB Output is correct
14 Correct 1396 ms 8600 KB Output is correct
15 Correct 1238 ms 8588 KB Output is correct
16 Correct 2950 ms 8600 KB Output is correct
17 Correct 2822 ms 8604 KB Output is correct
18 Correct 3054 ms 8596 KB Output is correct
19 Correct 2670 ms 8596 KB Output is correct
20 Correct 2903 ms 8596 KB Output is correct
21 Correct 2699 ms 8596 KB Output is correct
22 Correct 3067 ms 8600 KB Output is correct
23 Correct 2731 ms 8600 KB Output is correct
24 Correct 3037 ms 8596 KB Output is correct
25 Correct 2669 ms 8596 KB Output is correct
26 Correct 2993 ms 8596 KB Output is correct
27 Correct 3136 ms 8604 KB Output is correct
28 Correct 4932 ms 8616 KB Output is correct
29 Correct 4739 ms 8628 KB Output is correct
30 Correct 4208 ms 8620 KB Output is correct
31 Incorrect 4003 ms 8612 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 8596 KB Output is correct
2 Correct 1299 ms 8596 KB Output is correct
3 Correct 1251 ms 8592 KB Output is correct
4 Correct 1503 ms 8596 KB Output is correct
5 Correct 1413 ms 8588 KB Output is correct
6 Correct 1443 ms 8592 KB Output is correct
7 Correct 1343 ms 8592 KB Output is correct
8 Correct 1297 ms 8532 KB Output is correct
9 Correct 1290 ms 8592 KB Output is correct
10 Correct 1389 ms 8592 KB Output is correct
11 Correct 1451 ms 8596 KB Output is correct
12 Correct 1361 ms 8592 KB Output is correct
13 Correct 1344 ms 8600 KB Output is correct
14 Correct 1396 ms 8600 KB Output is correct
15 Correct 1238 ms 8588 KB Output is correct
16 Correct 2950 ms 8600 KB Output is correct
17 Correct 2822 ms 8604 KB Output is correct
18 Correct 3054 ms 8596 KB Output is correct
19 Correct 2670 ms 8596 KB Output is correct
20 Correct 2903 ms 8596 KB Output is correct
21 Correct 2699 ms 8596 KB Output is correct
22 Correct 3067 ms 8600 KB Output is correct
23 Correct 2731 ms 8600 KB Output is correct
24 Correct 3037 ms 8596 KB Output is correct
25 Correct 2669 ms 8596 KB Output is correct
26 Correct 2993 ms 8596 KB Output is correct
27 Correct 3136 ms 8604 KB Output is correct
28 Correct 4932 ms 8616 KB Output is correct
29 Correct 4739 ms 8628 KB Output is correct
30 Correct 4208 ms 8620 KB Output is correct
31 Incorrect 4003 ms 8612 KB Output isn't correct
32 Halted 0 ms 0 KB -