oj.uz

답안 #908711

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

int w,h;
vector<int>x,y;
vector<vector<int>>mat;
int arr[1000000];
const int TREE_SIZE=1<<20;
vector<pair<int,int>>tree[2*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 update(int l,int r,int 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());
    
    for(int i=vals[0];i<vals[1];i++)
        arr[i]+=mul;
    for(int i=vals[2];i<vals[3];i++)
        arr[i]+=mul;
    update(vals[0],vals[1],mul);
    update(vals[2],vals[3],mul);
}

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_sq(x,y,1);
    for(int i=TREE_SIZE;i<2*TREE_SIZE;i++)
        tree[i]={{0,1}};
}

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;*/
    for(int i=0;i<w*h;i++)
        if(arr[i]==4)
            res++;
    return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 84528 KB Output is correct
2 Correct 55 ms 84560 KB Output is correct
3 Correct 58 ms 84560 KB Output is correct
4 Correct 55 ms 84568 KB Output is correct
5 Correct 54 ms 84528 KB Output is correct
6 Correct 61 ms 84568 KB Output is correct
7 Correct 58 ms 84564 KB Output is correct
8 Correct 59 ms 84560 KB Output is correct
9 Correct 57 ms 84428 KB Output is correct
10 Correct 71 ms 84668 KB Output is correct
11 Correct 57 ms 84672 KB Output is correct
12 Correct 54 ms 84564 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 84528 KB Output is correct
2 Correct 55 ms 84560 KB Output is correct
3 Correct 58 ms 84560 KB Output is correct
4 Correct 55 ms 84568 KB Output is correct
5 Correct 54 ms 84528 KB Output is correct
6 Correct 61 ms 84568 KB Output is correct
7 Correct 58 ms 84564 KB Output is correct
8 Correct 59 ms 84560 KB Output is correct
9 Correct 57 ms 84428 KB Output is correct
10 Correct 71 ms 84668 KB Output is correct
11 Correct 57 ms 84672 KB Output is correct
12 Correct 54 ms 84564 KB Output is correct
13 Correct 213 ms 84872 KB Output is correct
14 Correct 254 ms 84816 KB Output is correct
15 Correct 252 ms 85328 KB Output is correct
16 Correct 155 ms 84816 KB Output is correct
17 Correct 222 ms 85076 KB Output is correct
18 Correct 155 ms 84816 KB Output is correct
19 Correct 157 ms 84860 KB Output is correct
20 Correct 154 ms 84824 KB Output is correct
21 Correct 158 ms 85328 KB Output is correct
22 Correct 161 ms 85340 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4018 ms 82768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 84816 KB Output is correct
2 Correct 564 ms 88888 KB Output is correct
3 Correct 3513 ms 115632 KB Output is correct
4 Execution timed out 4059 ms 82804 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 85516 KB Output is correct
2 Correct 99 ms 85580 KB Output is correct
3 Correct 107 ms 85456 KB Output is correct
4 Correct 217 ms 85692 KB Output is correct
5 Correct 1621 ms 86364 KB Output is correct
6 Execution timed out 4018 ms 166736 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 84528 KB Output is correct
2 Correct 55 ms 84560 KB Output is correct
3 Correct 58 ms 84560 KB Output is correct
4 Correct 55 ms 84568 KB Output is correct
5 Correct 54 ms 84528 KB Output is correct
6 Correct 61 ms 84568 KB Output is correct
7 Correct 58 ms 84564 KB Output is correct
8 Correct 59 ms 84560 KB Output is correct
9 Correct 57 ms 84428 KB Output is correct
10 Correct 71 ms 84668 KB Output is correct
11 Correct 57 ms 84672 KB Output is correct
12 Correct 54 ms 84564 KB Output is correct
13 Correct 213 ms 84872 KB Output is correct
14 Correct 254 ms 84816 KB Output is correct
15 Correct 252 ms 85328 KB Output is correct
16 Correct 155 ms 84816 KB Output is correct
17 Correct 222 ms 85076 KB Output is correct
18 Correct 155 ms 84816 KB Output is correct
19 Correct 157 ms 84860 KB Output is correct
20 Correct 154 ms 84824 KB Output is correct
21 Correct 158 ms 85328 KB Output is correct
22 Correct 161 ms 85340 KB Output is correct
23 Execution timed out 4018 ms 82768 KB Time limit exceeded
24 Halted 0 ms 0 KB -