oj.uz

Submission #908708

# Submission time Handle Problem Language Result Execution time Memory
908708 2024-01-16T17:23:27 Z JakobZorz Seats (IOI18_seats) C++17
11 / 100
 4000 ms 141140 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<int>tree[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 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)
        cout<<i<<" ";
    cout<<endl;*/
    for(int i=vals[0];i<vals[1];i++)
        arr[i]+=mul;
    for(int i=vals[2];i<vals[3];i++)
        arr[i]+=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);
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 50012 KB Output is correct
2 Correct 21 ms 50012 KB Output is correct
3 Correct 24 ms 50016 KB Output is correct
4 Correct 22 ms 50012 KB Output is correct
5 Correct 21 ms 49800 KB Output is correct
6 Correct 24 ms 50012 KB Output is correct
7 Correct 25 ms 50004 KB Output is correct
8 Correct 22 ms 50012 KB Output is correct
9 Correct 21 ms 50012 KB Output is correct
10 Correct 24 ms 50228 KB Output is correct
11 Correct 23 ms 50012 KB Output is correct
12 Correct 23 ms 50208 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 50012 KB Output is correct
2 Correct 21 ms 50012 KB Output is correct
3 Correct 24 ms 50016 KB Output is correct
4 Correct 22 ms 50012 KB Output is correct
5 Correct 21 ms 49800 KB Output is correct
6 Correct 24 ms 50012 KB Output is correct
7 Correct 25 ms 50004 KB Output is correct
8 Correct 22 ms 50012 KB Output is correct
9 Correct 21 ms 50012 KB Output is correct
10 Correct 24 ms 50228 KB Output is correct
11 Correct 23 ms 50012 KB Output is correct
12 Correct 23 ms 50208 KB Output is correct
13 Correct 164 ms 50332 KB Output is correct
14 Correct 217 ms 50352 KB Output is correct
15 Correct 212 ms 50860 KB Output is correct
16 Correct 112 ms 50264 KB Output is correct
17 Correct 178 ms 50572 KB Output is correct
18 Correct 112 ms 50368 KB Output is correct
19 Correct 112 ms 50352 KB Output is correct
20 Correct 111 ms 50348 KB Output is correct
21 Correct 115 ms 50860 KB Output is correct
22 Correct 113 ms 50264 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4026 ms 89172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 50264 KB Output is correct
2 Correct 506 ms 55416 KB Output is correct
3 Correct 3339 ms 89164 KB Output is correct
4 Execution timed out 4014 ms 89428 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 51404 KB Output is correct
2 Correct 64 ms 51404 KB Output is correct
3 Correct 72 ms 51408 KB Output is correct
4 Correct 168 ms 51412 KB Output is correct
5 Correct 1526 ms 52484 KB Output is correct
6 Execution timed out 4032 ms 141140 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 50012 KB Output is correct
2 Correct 21 ms 50012 KB Output is correct
3 Correct 24 ms 50016 KB Output is correct
4 Correct 22 ms 50012 KB Output is correct
5 Correct 21 ms 49800 KB Output is correct
6 Correct 24 ms 50012 KB Output is correct
7 Correct 25 ms 50004 KB Output is correct
8 Correct 22 ms 50012 KB Output is correct
9 Correct 21 ms 50012 KB Output is correct
10 Correct 24 ms 50228 KB Output is correct
11 Correct 23 ms 50012 KB Output is correct
12 Correct 23 ms 50208 KB Output is correct
13 Correct 164 ms 50332 KB Output is correct
14 Correct 217 ms 50352 KB Output is correct
15 Correct 212 ms 50860 KB Output is correct
16 Correct 112 ms 50264 KB Output is correct
17 Correct 178 ms 50572 KB Output is correct
18 Correct 112 ms 50368 KB Output is correct
19 Correct 112 ms 50352 KB Output is correct
20 Correct 111 ms 50348 KB Output is correct
21 Correct 115 ms 50860 KB Output is correct
22 Correct 113 ms 50264 KB Output is correct
23 Execution timed out 4026 ms 89172 KB Time limit exceeded
24 Halted 0 ms 0 KB -