oj.uz

답안 #908744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908744 2024-01-16T18:52:28 Z JakobZorz 자리 배치 (IOI18_seats) C++17
100 / 100
 3616 ms 225356 KB 
#include"seats.h"
#include<iostream>
#include<algorithm>
using namespace std;

const int TREE_SIZE=1<<20;

int w,h;
vector<int>x,y;
vector<vector<int>>mat;
vector<pair<int,int>>tree[2*TREE_SIZE];
int arr0[TREE_SIZE];
int lazy[2*TREE_SIZE];

int get_mat(int x,int y){
    if(x<0||x>=w||y<0||y>=h)
        return w*h;
    return mat[x][y];
}

void push_lazy(int node){
    if(lazy[node]!=0){
        if(node<TREE_SIZE){
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        for(auto&i:tree[node])
            i.first+=lazy[node];
        lazy[node]=0;
    }
}

void update_node(int node){
    if(node<TREE_SIZE){
        tree[node].clear();
        int i1=0,i2=0;
        int s1=tree[2*node].size();
        int s2=tree[2*node+1].size();
        while(tree[node].size()<4&&(i1<s1||i2<s2)){
            if(i2==s2){
                tree[node].push_back(tree[2*node][i1]);
                i1++;
                continue;
            }
            
            if(i1==s1){
                tree[node].push_back(tree[2*node+1][i2]);
                i2++;
                continue;
            }
            
            if(tree[2*node][i1].first==tree[2*node+1][i2].first){
                tree[node].emplace_back(tree[2*node][i1].first,tree[2*node][i1].second+tree[2*node+1][i2].second);
                i1++;
                i2++;
                continue;
            }
            
            if(tree[2*node][i1].first<tree[2*node+1][i2].first){
                tree[node].push_back(tree[2*node][i1]);
                i1++;
            }else{
                tree[node].push_back(tree[2*node+1][i2]);
                i2++;
            }
        }
    }
}

void update(int node,int rl,int rr,int l,int r,int v){
    push_lazy(node);
    if(r<=rl||rr<=l)
        return;
    if(l<=rl&&rr<=r){
        lazy[node]+=v;
        push_lazy(node);
        return;
    }
    
    int mid=(rl+rr)/2;
    update(2*node,rl,mid,l,r,v);
    update(2*node+1,mid,rr,l,r,v);
    update_node(node);
}

void update(int l,int r,int v){
    update(1,0,TREE_SIZE,l,r,v);
}

void upd_sq(int x,int y,int mul){ // 1 for adding and -1 for removing
    vector<int>vals={get_mat(x,y),get_mat(x+1,y),get_mat(x,y+1),get_mat(x+1,y+1)};
    sort(vals.begin(),vals.end());
    
    update(vals[0],vals[1],mul);
    update(vals[2],vals[3],mul);
}

void upd_sq2(int x,int y){
    vector<int>vals={get_mat(x,y),get_mat(x+1,y),get_mat(x,y+1),get_mat(x+1,y+1)};
    sort(vals.begin(),vals.end());
    
    arr0[vals[0]]++;
    arr0[vals[1]]--;
    arr0[vals[2]]++;
    arr0[vals[3]]--;
}

void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
    x=C;
    y=R;
    h=H;
    w=W;
    mat=vector<vector<int>>(w,vector<int>(h));
    for(int i=0;i<w*h;i++)
        mat[x[i]][y[i]]=i;
    
    for(int x=-1;x<w;x++)
        for(int y=-1;y<h;y++)
            upd_sq2(x,y);
    
    int cv=0;
    for(int i=TREE_SIZE;i<2*TREE_SIZE;i++){
        cv+=arr0[i-TREE_SIZE];
        tree[i]={{cv,1}};
    }
    for(int i=TREE_SIZE-1;i>0;i--)
        update_node(i);
}

int swap_seats(int a,int b){
    upd_sq(x[a]-1,y[a]-1,-1);
    upd_sq(x[a]-1,y[a],-1);
    upd_sq(x[a],y[a]-1,-1);
    upd_sq(x[a],y[a],-1);
    upd_sq(x[b]-1,y[b]-1,-1);
    upd_sq(x[b]-1,y[b],-1);
    upd_sq(x[b],y[b]-1,-1);
    upd_sq(x[b],y[b],-1);
    swap(mat[x[a]][y[a]],mat[x[b]][y[b]]);
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    upd_sq(x[a]-1,y[a]-1,1);
    upd_sq(x[a]-1,y[a],1);
    upd_sq(x[a],y[a]-1,1);
    upd_sq(x[a],y[a],1);
    upd_sq(x[b]-1,y[b]-1,1);
    upd_sq(x[b]-1,y[b],1);
    upd_sq(x[b],y[b]-1,1);
    upd_sq(x[b],y[b],1);
    
    int res=0;
    for(auto i:tree[1]){
        if(i.first==4)
            res=i.second;
    }
    return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 119368 KB Output is correct
2 Correct 192 ms 119268 KB Output is correct
3 Correct 212 ms 119368 KB Output is correct
4 Correct 189 ms 119404 KB Output is correct
5 Correct 177 ms 119420 KB Output is correct
6 Correct 199 ms 119376 KB Output is correct
7 Correct 233 ms 119284 KB Output is correct
8 Correct 197 ms 119376 KB Output is correct
9 Correct 198 ms 119376 KB Output is correct
10 Correct 205 ms 121440 KB Output is correct
11 Correct 204 ms 119632 KB Output is correct
12 Correct 188 ms 121276 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 119368 KB Output is correct
2 Correct 192 ms 119268 KB Output is correct
3 Correct 212 ms 119368 KB Output is correct
4 Correct 189 ms 119404 KB Output is correct
5 Correct 177 ms 119420 KB Output is correct
6 Correct 199 ms 119376 KB Output is correct
7 Correct 233 ms 119284 KB Output is correct
8 Correct 197 ms 119376 KB Output is correct
9 Correct 198 ms 119376 KB Output is correct
10 Correct 205 ms 121440 KB Output is correct
11 Correct 204 ms 119632 KB Output is correct
12 Correct 188 ms 121276 KB Output is correct
13 Correct 276 ms 119632 KB Output is correct
14 Correct 289 ms 121680 KB Output is correct
15 Correct 232 ms 120304 KB Output is correct
16 Correct 207 ms 119640 KB Output is correct
17 Correct 244 ms 122192 KB Output is correct
18 Correct 263 ms 119792 KB Output is correct
19 Correct 232 ms 119636 KB Output is correct
20 Correct 229 ms 121820 KB Output is correct
21 Correct 221 ms 120316 KB Output is correct
22 Correct 218 ms 119636 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 729 ms 154928 KB Output is correct
2 Correct 575 ms 170172 KB Output is correct
3 Correct 522 ms 165080 KB Output is correct
4 Correct 557 ms 166644 KB Output is correct
5 Correct 574 ms 166188 KB Output is correct
6 Correct 540 ms 165380 KB Output is correct
7 Correct 546 ms 165280 KB Output is correct
8 Correct 562 ms 166732 KB Output is correct
9 Correct 545 ms 165212 KB Output is correct
10 Correct 538 ms 165100 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 119632 KB Output is correct
2 Correct 328 ms 126360 KB Output is correct
3 Correct 516 ms 154356 KB Output is correct
4 Correct 737 ms 154964 KB Output is correct
5 Correct 497 ms 215524 KB Output is correct
6 Correct 551 ms 170736 KB Output is correct
7 Correct 523 ms 184156 KB Output is correct
8 Correct 555 ms 166648 KB Output is correct
9 Correct 524 ms 165336 KB Output is correct
10 Correct 514 ms 169928 KB Output is correct
11 Correct 489 ms 172448 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 824 ms 122408 KB Output is correct
2 Correct 858 ms 120560 KB Output is correct
3 Correct 867 ms 122196 KB Output is correct
4 Correct 934 ms 120444 KB Output is correct
5 Correct 1145 ms 121360 KB Output is correct
6 Correct 1840 ms 206860 KB Output is correct
7 Correct 1774 ms 205416 KB Output is correct
8 Correct 1735 ms 225356 KB Output is correct
9 Correct 2149 ms 223436 KB Output is correct
10 Correct 1568 ms 221384 KB Output is correct
11 Correct 1577 ms 221568 KB Output is correct
12 Correct 1425 ms 222152 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 119368 KB Output is correct
2 Correct 192 ms 119268 KB Output is correct
3 Correct 212 ms 119368 KB Output is correct
4 Correct 189 ms 119404 KB Output is correct
5 Correct 177 ms 119420 KB Output is correct
6 Correct 199 ms 119376 KB Output is correct
7 Correct 233 ms 119284 KB Output is correct
8 Correct 197 ms 119376 KB Output is correct
9 Correct 198 ms 119376 KB Output is correct
10 Correct 205 ms 121440 KB Output is correct
11 Correct 204 ms 119632 KB Output is correct
12 Correct 188 ms 121276 KB Output is correct
13 Correct 276 ms 119632 KB Output is correct
14 Correct 289 ms 121680 KB Output is correct
15 Correct 232 ms 120304 KB Output is correct
16 Correct 207 ms 119640 KB Output is correct
17 Correct 244 ms 122192 KB Output is correct
18 Correct 263 ms 119792 KB Output is correct
19 Correct 232 ms 119636 KB Output is correct
20 Correct 229 ms 121820 KB Output is correct
21 Correct 221 ms 120316 KB Output is correct
22 Correct 218 ms 119636 KB Output is correct
23 Correct 729 ms 154928 KB Output is correct
24 Correct 575 ms 170172 KB Output is correct
25 Correct 522 ms 165080 KB Output is correct
26 Correct 557 ms 166644 KB Output is correct
27 Correct 574 ms 166188 KB Output is correct
28 Correct 540 ms 165380 KB Output is correct
29 Correct 546 ms 165280 KB Output is correct
30 Correct 562 ms 166732 KB Output is correct
31 Correct 545 ms 165212 KB Output is correct
32 Correct 538 ms 165100 KB Output is correct
33 Correct 260 ms 119632 KB Output is correct
34 Correct 328 ms 126360 KB Output is correct
35 Correct 516 ms 154356 KB Output is correct
36 Correct 737 ms 154964 KB Output is correct
37 Correct 497 ms 215524 KB Output is correct
38 Correct 551 ms 170736 KB Output is correct
39 Correct 523 ms 184156 KB Output is correct
40 Correct 555 ms 166648 KB Output is correct
41 Correct 524 ms 165336 KB Output is correct
42 Correct 514 ms 169928 KB Output is correct
43 Correct 489 ms 172448 KB Output is correct
44 Correct 824 ms 122408 KB Output is correct
45 Correct 858 ms 120560 KB Output is correct
46 Correct 867 ms 122196 KB Output is correct
47 Correct 934 ms 120444 KB Output is correct
48 Correct 1145 ms 121360 KB Output is correct
49 Correct 1840 ms 206860 KB Output is correct
50 Correct 1774 ms 205416 KB Output is correct
51 Correct 1735 ms 225356 KB Output is correct
52 Correct 2149 ms 223436 KB Output is correct
53 Correct 1568 ms 221384 KB Output is correct
54 Correct 1577 ms 221568 KB Output is correct
55 Correct 1425 ms 222152 KB Output is correct
56 Correct 899 ms 121300 KB Output is correct
57 Correct 1126 ms 121052 KB Output is correct
58 Correct 1362 ms 121456 KB Output is correct
59 Correct 2648 ms 176420 KB Output is correct
60 Correct 3616 ms 173932 KB Output is correct
61 Correct 2037 ms 173016 KB Output is correct
62 Correct 1622 ms 195552 KB Output is correct
63 Correct 3109 ms 187784 KB Output is correct
64 Correct 2276 ms 176220 KB Output is correct
65 Correct 1945 ms 173528 KB Output is correct
66 Correct 2601 ms 176468 KB Output is correct
67 Correct 2187 ms 173432 KB Output is correct
68 Correct 1772 ms 172344 KB Output is correct
69 Correct 2723 ms 173176 KB Output is correct