oj.uz

답안 #908741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908741 2024-01-16T18:38:54 Z JakobZorz 자리 배치 (IOI18_seats) C++17
11 / 100
 4000 ms 235796 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 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());
    
    /*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 i=TREE_SIZE;i<2*TREE_SIZE;i++)
        tree[i]={{0,1}};
    for(int i=TREE_SIZE-1;i>0;i--)
        update_node(i);
    
    //update(100,1000,1);
    //update(500,1500,-1);
    /*for(auto i:tree[1]){
        cout<<"p "<<i.first<<" "<<i.second<<"\n";
    }*/
    
    for(int x=-1;x<w;x++)
        for(int y=-1;y<h;y++)
            upd_sq(x,y,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]){
        //cout<<"p "<<i.first<<" "<<i.second<<"\n";
        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 180 ms 117328 KB Output is correct
2 Correct 193 ms 117336 KB Output is correct
3 Correct 203 ms 119360 KB Output is correct
4 Correct 184 ms 119364 KB Output is correct
5 Correct 179 ms 121668 KB Output is correct
6 Correct 197 ms 117332 KB Output is correct
7 Correct 205 ms 117328 KB Output is correct
8 Correct 195 ms 117332 KB Output is correct
9 Correct 192 ms 121428 KB Output is correct
10 Correct 202 ms 121424 KB Output is correct
11 Correct 195 ms 117368 KB Output is correct
12 Correct 177 ms 119380 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 117328 KB Output is correct
2 Correct 193 ms 117336 KB Output is correct
3 Correct 203 ms 119360 KB Output is correct
4 Correct 184 ms 119364 KB Output is correct
5 Correct 179 ms 121668 KB Output is correct
6 Correct 197 ms 117332 KB Output is correct
7 Correct 205 ms 117328 KB Output is correct
8 Correct 195 ms 117332 KB Output is correct
9 Correct 192 ms 121428 KB Output is correct
10 Correct 202 ms 121424 KB Output is correct
11 Correct 195 ms 117368 KB Output is correct
12 Correct 177 ms 119380 KB Output is correct
13 Correct 277 ms 119892 KB Output is correct
14 Correct 307 ms 117764 KB Output is correct
15 Correct 259 ms 118164 KB Output is correct
16 Correct 216 ms 119680 KB Output is correct
17 Correct 267 ms 120052 KB Output is correct
18 Correct 271 ms 119868 KB Output is correct
19 Correct 235 ms 117868 KB Output is correct
20 Correct 243 ms 119628 KB Output is correct
21 Correct 268 ms 120408 KB Output is correct
22 Correct 227 ms 117660 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 117844 KB Output is correct
2 Correct 492 ms 125524 KB Output is correct
3 Correct 2004 ms 167260 KB Output is correct
4 Execution timed out 4032 ms 164712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 785 ms 118236 KB Output is correct
2 Correct 856 ms 120292 KB Output is correct
3 Correct 879 ms 120512 KB Output is correct
4 Correct 931 ms 122484 KB Output is correct
5 Correct 1173 ms 119272 KB Output is correct
6 Correct 3353 ms 223476 KB Output is correct
7 Execution timed out 4040 ms 235796 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 117328 KB Output is correct
2 Correct 193 ms 117336 KB Output is correct
3 Correct 203 ms 119360 KB Output is correct
4 Correct 184 ms 119364 KB Output is correct
5 Correct 179 ms 121668 KB Output is correct
6 Correct 197 ms 117332 KB Output is correct
7 Correct 205 ms 117328 KB Output is correct
8 Correct 195 ms 117332 KB Output is correct
9 Correct 192 ms 121428 KB Output is correct
10 Correct 202 ms 121424 KB Output is correct
11 Correct 195 ms 117368 KB Output is correct
12 Correct 177 ms 119380 KB Output is correct
13 Correct 277 ms 119892 KB Output is correct
14 Correct 307 ms 117764 KB Output is correct
15 Correct 259 ms 118164 KB Output is correct
16 Correct 216 ms 119680 KB Output is correct
17 Correct 267 ms 120052 KB Output is correct
18 Correct 271 ms 119868 KB Output is correct
19 Correct 235 ms 117868 KB Output is correct
20 Correct 243 ms 119628 KB Output is correct
21 Correct 268 ms 120408 KB Output is correct
22 Correct 227 ms 117660 KB Output is correct
23 Execution timed out 4051 ms 164832 KB Time limit exceeded
24 Halted 0 ms 0 KB -