Submission #94190

#	Time	Username	Problem	Language	Result	Execution time	Memory
94190		someone_aa	Seats (IOI18_seats)	C++17	11 / 100	4051 ms	63068 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int maxn = 1100;
pair<int,int>cords[maxn*maxn];
int h, w;
int result[maxn * maxn];
int cnt;

struct node {
public:
    pair<int,int>minv, maxv;
} tree[4*maxn*maxn];

node mergef(node a, node b) {
    node c;
    c.minv.first = min(a.minv.first, b.minv.first);
    c.minv.second = min(a.minv.second, b.minv.second);
    c.maxv.first = max(a.maxv.first, b.maxv.first);
    c.maxv.second = max(a.maxv.second, b.maxv.second);
    return c;
}

void update(int x, pair<int,int> uval, int li=0, int ri=h*w-1, int index=1) {
    if(li == ri) {
        tree[index].minv.first = tree[index].maxv.first = uval.first;
        tree[index].minv.second = tree[index].maxv.second = uval.second;
    }
    else {
        int mid = (li+ri)/2;
        if(x<=mid) update(x, uval, li, mid, 2*index);
        else update(x, uval, mid+1, ri, 2*index+1);
        tree[index] = mergef(tree[2*index], tree[2*index+1]);
    }
}

node query(int ql, int qr, int li=0, int ri=h*w-1, int index=1) {
    if(li > qr || ri < ql) return {{INT_MAX, INT_MAX}, {INT_MIN, INT_MIN}};
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li+ri)/2;
        return mergef(query(ql,qr,li,mid,2*index), query(ql,qr,mid+1,ri,2*index+1));
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H; w = W;
    for(int i=0;i<H*W;i++) {
        cords[i].first = R[i];
        cords[i].second = C[i];
        update(i, cords[i]);
    }

    for(int i=0;i<H*W;i++) {
        node x = query(0, i);
        int min_x = x.minv.first;
        int min_y = x.minv.second;
        int max_x = x.maxv.first;
        int max_y = x.maxv.second;

        if(i + 1 == (max_x-min_x+1)*(max_y-min_y+1)) {
            result[i] = 1;
            cnt++;
        }
    }
}

int swap_seats(int a, int b) {
    swap(cords[a], cords[b]);
    update(a, cords[a]);
    update(b, cords[b]);

    if(a > b) swap(a, b);

    for(int i=a;i<=b;i++) {
        node x = query(0, i);

        int min_x = x.minv.first;
        int min_y = x.minv.second;

        int max_x = x.maxv.first;
        int max_y = x.maxv.second;

        if(i + 1 == (max_x-min_x+1)*(max_y-min_y+1)) {
            if(result[i] == 1) continue;
            else {
                result[i] = 1;
                cnt++;
            }
        }
        else {
            if(result[i] == 1) {
                result[i] = 0;
                cnt--;
            }
        }
    }
    return cnt;
}

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