oj.uz

답안 #600734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600734 2022-07-21T07:30:59 Z 장태환(#8468) Arranging Tickets (JOI17_arranging_tickets) C++17
10 / 100
 891 ms 340 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;
    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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 312 KB Output is correct
2 Correct 408 ms 312 KB Output is correct
3 Correct 359 ms 312 KB Output is correct
4 Correct 406 ms 316 KB Output is correct
5 Correct 401 ms 316 KB Output is correct
6 Correct 361 ms 312 KB Output is correct
7 Correct 440 ms 312 KB Output is correct
8 Correct 402 ms 312 KB Output is correct
9 Correct 364 ms 308 KB Output is correct
10 Correct 413 ms 212 KB Output is correct
11 Correct 418 ms 308 KB Output is correct
12 Correct 464 ms 312 KB Output is correct
13 Correct 366 ms 312 KB Output is correct
14 Correct 436 ms 312 KB Output is correct
15 Correct 466 ms 320 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 312 KB Output is correct
2 Correct 408 ms 312 KB Output is correct
3 Correct 359 ms 312 KB Output is correct
4 Correct 406 ms 316 KB Output is correct
5 Correct 401 ms 316 KB Output is correct
6 Correct 361 ms 312 KB Output is correct
7 Correct 440 ms 312 KB Output is correct
8 Correct 402 ms 312 KB Output is correct
9 Correct 364 ms 308 KB Output is correct
10 Correct 413 ms 212 KB Output is correct
11 Correct 418 ms 308 KB Output is correct
12 Correct 464 ms 312 KB Output is correct
13 Correct 366 ms 312 KB Output is correct
14 Correct 436 ms 312 KB Output is correct
15 Correct 466 ms 320 KB Output is correct
16 Incorrect 891 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 312 KB Output is correct
2 Correct 408 ms 312 KB Output is correct
3 Correct 359 ms 312 KB Output is correct
4 Correct 406 ms 316 KB Output is correct
5 Correct 401 ms 316 KB Output is correct
6 Correct 361 ms 312 KB Output is correct
7 Correct 440 ms 312 KB Output is correct
8 Correct 402 ms 312 KB Output is correct
9 Correct 364 ms 308 KB Output is correct
10 Correct 413 ms 212 KB Output is correct
11 Correct 418 ms 308 KB Output is correct
12 Correct 464 ms 312 KB Output is correct
13 Correct 366 ms 312 KB Output is correct
14 Correct 436 ms 312 KB Output is correct
15 Correct 466 ms 320 KB Output is correct
16 Incorrect 891 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 312 KB Output is correct
2 Correct 408 ms 312 KB Output is correct
3 Correct 359 ms 312 KB Output is correct
4 Correct 406 ms 316 KB Output is correct
5 Correct 401 ms 316 KB Output is correct
6 Correct 361 ms 312 KB Output is correct
7 Correct 440 ms 312 KB Output is correct
8 Correct 402 ms 312 KB Output is correct
9 Correct 364 ms 308 KB Output is correct
10 Correct 413 ms 212 KB Output is correct
11 Correct 418 ms 308 KB Output is correct
12 Correct 464 ms 312 KB Output is correct
13 Correct 366 ms 312 KB Output is correct
14 Correct 436 ms 312 KB Output is correct
15 Correct 466 ms 320 KB Output is correct
16 Incorrect 891 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 312 KB Output is correct
2 Correct 408 ms 312 KB Output is correct
3 Correct 359 ms 312 KB Output is correct
4 Correct 406 ms 316 KB Output is correct
5 Correct 401 ms 316 KB Output is correct
6 Correct 361 ms 312 KB Output is correct
7 Correct 440 ms 312 KB Output is correct
8 Correct 402 ms 312 KB Output is correct
9 Correct 364 ms 308 KB Output is correct
10 Correct 413 ms 212 KB Output is correct
11 Correct 418 ms 308 KB Output is correct
12 Correct 464 ms 312 KB Output is correct
13 Correct 366 ms 312 KB Output is correct
14 Correct 436 ms 312 KB Output is correct
15 Correct 466 ms 320 KB Output is correct
16 Incorrect 891 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -