Submission #1135891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135891		vibeduck	Seats (IOI18_seats)	C++20	0 / 100	4094 ms	64776 KiB

seats

#include "seats.h"
#include <bits/stdc++.h> 
using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
//#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

int H, W;
//const int mxh = 1e4, mxw = 1e4;
pii coord[1000000];

// PREFIX BOUNDING BOX SEGTREE
const pair<pii, pii> defval = {{1e18, 1e18}, {-1e18, -1e18}}; // tl min br max
pair<pii, pii> seg[4 * 1000000];

pair<pii, pii> segfunction(pair<pii, pii> x, pair<pii, pii> y) {
    return {{min(x.fi.fi, y.fi.fi), min(x.fi.se, y.fi.se)}, {max(x.se.fi, y.se.fi), max(x.se.se, y.se.se)}};
}

pair<pii, pii> query(int l, int r, int pos, int ql, int qr) {
    if (ql > r || l > qr) {
        return defval;
    }
    if (ql <= l && r <= qr) {
        return seg[pos];
    }
    int mid = (l + r) / 2;
    return segfunction(query(l, mid, pos * 2, ql, qr), query(mid + 1, r, pos * 2 + 1, ql, qr));
}

void build(int l, int r, int pos) {
    if (l == r) {
        seg[pos] = {coord[l], coord[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, pos * 2);
    build(mid + 1, r, pos * 2 + 1);
    seg[pos] = segfunction(seg[pos * 2], seg[pos * 2 + 1]);
}

void update(int l, int r, int pos, int qpos, pii qval) {
    if (l == r) {
        seg[pos] = {qval, qval};
        return;
    }

    int mid = (l + r) / 2;
    if (qpos <= mid) {
        update(l, mid, pos * 2, qpos, qval);
    } else {
        update(mid + 1, r, pos * 2 + 1, qpos, qval);
    }

    seg[pos] = segfunction(seg[pos * 2], seg[pos * 2 + 1]);
}




// ANSWER SEGTREE
const int defval1 = 0;
int seg1[4 * 1000000];

int segfunction1(int x, int y) {
    return x + y;
}

int query1(int l, int r, int pos, int ql, int qr) {
    if (ql > r || l > qr) {
        return defval1;
    }
    if (ql <= l && r <= qr) {
        return seg1[pos];
    }
    int mid = (l + r) / 2;
    return segfunction1(query1(l, mid, pos * 2, ql, qr), query1(mid + 1, r, pos * 2 + 1, ql, qr));
}

void update1(int l, int r, int pos, int qpos, int qval) {
    if (l == r) {
        seg1[pos] = qval;
        return;
    }

    int mid = (l + r) / 2;
    if (qpos <= mid) {
        update1(l, mid, pos * 2, qpos, qval);
    } else {
        update1(mid + 1, r, pos * 2 + 1, qpos, qval);
    }

    seg1[pos] = segfunction1(seg1[pos * 2], seg1[pos * 2 + 1]);
}











void give_initial_chart(int H1, int W1, vi R, vi C) {
    H = H1; W = W1;
    for (int i = 0; i < H * W; i++) {
        coord[i] = {R[i], C[i]};
    }
    build(0, H*W - 1, 1);
    for (int i = 0; i < H * W; i++) {
        pair<pii, pii> bound = query(0, H*W - 1, 1, 0, i);
        pii tl = bound.fi, br = bound.se;
        int ans = ((br.fi - tl.fi + 1) * (br.se - tl.se + 1) == (i + 1));
        //cout << i << ": tl->{" << bound.fi.fi << " " << bound.fi.se << "} br->{" << bound.se.fi << " " << bound.se.se << "}\n";
        update1(0, H*W - 1, 1, i, ans);
    }
}

int swap_seats(int a, int b) {
    swap(coord[a], coord[b]);
    update(0, H*W - 1, 1, a, coord[a]);
    update(0, H*W - 1, 1, b, coord[b]);
    for (int i = a; i <= b; i++) {
        pair<pii, pii> bound = query(0, H*W - 1, 1, 0, i);
        pii tl = bound.fi, br = bound.se;
        int ans = ((br.fi - tl.fi + 1) * (br.se - tl.se + 1) == (i + 1));
        update1(0, H*W - 1, 1, i, ans);
    }
    return query1(0, H*W - 1, 1, 0, H*W - 1);
}

/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/

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