Submission #605559

#	Time	Username	Problem	Language	Result	Execution time	Memory
605559		AmirElarbi	Seats (IOI18_seats)	C++14	0 / 100	4041 ms	75832 KiB

seats

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e3+5
#define V 450
using namespace std;
const int MOD = 1e9;
const int nax = 1e3+5;
#include "seats.h"

ii st[nax][nax*4][2];
void update(int v, int l, int r, int pos, int x , int val, int ind){
    if(l > pos || r < pos) return;
    if(l ==r){
        st[x][v][ind] = {val,val};
        return;
    }
    int md = (l+r)/2;
    update(v*2, l, md, pos,x, val, ind);
    update(v*2+1, md+1, r, pos,x, val, ind);
    st[x][v][ind].fi = min(st[x][v*2][ind].fi,st[x][v*2+1][ind].fi);
    st[x][v][ind].se = max(st[x][v*2][ind].se,st[x][v*2+1][ind].se);
}
ii query(int v, int l,int r, int i, int j, int x,int ind){
    if(i > r || j < l) return {INF,0};
    if(i <= l && r <= j) return st[x][v][ind];
    int md = (l+r)/2;
    return min(query(v*2,l,md,i,j,x,ind), query(v*2+1, md+1, r, i, j,x, ind));
}
vi r,c;
int w,h, cur = 0;
vi mn1, mx1, mn2, mx2, res;
void give_initial_chart(int H, int W, vi R, vi C) {
    r = R;
    c = C;
    w = W;
    h = H;
    for (int i = 0; i < w*h; ++i)
    {
        update(1, 0, h-1 , r[i], c[i], i, 0);
        update(1, 0, w-1 , c[i], r[i], i, 1);
    }
}

int swap_seats(int a, int b) {
    if(a > b) swap(a,b);
    update(1, 0, h-1 , r[a], c[a], b, 0);
    update(1, 0, w-1 , c[a], r[a], b, 1);
    update(1, 0, h-1 , r[b], c[b], a, 0);
    update(1, 0, w-1 , c[b], r[b], a, 1);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    int mnr = r[0], mnc = c[0], mxr = r[0], mxc = c[0], res = 1, mx = 0;
    while((mxr-mnr+1)*(mxc-mnc+1) != h*w){
        ii up = {INF,INF}, down = {INF,INF}, right = {INF,INF}, left = {INF,INF};
        if(mnr > 0) up = query(1,0,w-1,mnc,mxc, mnr-1, 1); 
        if(mxr < h-1) down = query(1,0,w-1,mnc,mxc, mxr+1, 1); 
        if(mnc > 0) left = query(1,0,h-1,mnr,mxr, mnc-1, 0); 
        if(mxc < w-1) right = query(1,0,h-1,mnr,mxr, mxc+1, 0); 
        ii mn = min(up,min(down,min(left,right)));
        if(mn == up) mnr--, mx = max(mx, up.se);
        if(mn == down) mxr++, mx = max(mx, down.se);
        if(mn == left) mnc--, mx = max(mx, left.se);
        if(mn == right) mxc++, mx = max(mx, right.se);
        if(mx+1 == (mxr-mnr+1)*(mxc-mnc+1)) res++;
    }
    return res;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30