Submission #838623

#	Time	Username	Problem	Language	Result	Execution time	Memory
838623		FulopMate	Seats (IOI18_seats)	C++17	31 / 100	4075 ms	64428 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

struct coords {
    int a, b, c, d;
    coords(){}
    coords(int aa, int bb, int cc, int dd) : a(aa), b(bb), c(cc), d(dd) {}
    coords(coords &x, coords &y){
        a = min(x.a, y.a);
        b = max(x.b, y.b);
        c = min(x.c, y.c);
        d = max(x.d, y.d);
    }
};

int n;
int h, w;
vector<coords> st;

void update(int i, coords d){
    i += n;
    st[i] = d;
    for(i /= 2; i > 0; i /= 2){
        st[i] = coords(st[i*2], st[i*2+1]);
    }
}

coords query(int l, int r){
    l += n; r += n;
    coords ans = st[l];
    while(l <= r){
        if(l%2){
            ans = coords(ans, st[l++]);
        }
        if(r%2==0){
            ans = coords(ans, st[r--]);
        }
        l /= 2;
        r /= 2;
    }
    return ans;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H*W;
    h = H, w = W;
    st.resize(2*n);
    for(int i = 0; i < n; i++){
        update(i, coords(R[i], R[i], C[i], C[i]));
    }
}

int swap_seats(int x, int y) {
    coords xc = query(x, x), yc = query(y, y);
    update(y, xc); update(x, yc);
    int i = 0;
    int ans = 0;
    for(; i < n;){
        coords cc = query(0, i);
        if((cc.b-cc.a+1)*(cc.d-cc.c+1) == i+1){
            ans++;
            i++;
        } else {
            i = (cc.b-cc.a+1)*(cc.d-cc.c+1)-1;
        }
    }
    return ans;
}

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