Submission #417668

#	Time	Username	Problem	Language	Result	Execution time	Memory
417668		ja_kingy	Seats (IOI18_seats)	C++14	100 / 100	2973 ms	118820 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> grid;
vector<int> r,c;
 
const int SZ = 1<<20;
struct LazyST {
    int sz, mn[SZ*2], lz[SZ*2], cnt[SZ*2];
    void build(vector<int>& vals, int l, int r, int t = 1) {
        if (t == 1) sz = vals.size();
        if (r - l == 1) {
            mn[t] = vals[l];
            cnt[t] = 1;
        } else {
            int m = l+r>>1;
            build(vals, l, m, t*2);
            build(vals, m, r, t*2+1);
            pull(t);
        }
    }
    void pull(int t) {
        mn[t] = min(mn[t*2], mn[t*2+1]);
        cnt[t] = 0;
        if (mn[t*2] == mn[t]) cnt[t] += cnt[t*2];
        if (mn[t*2+1] == mn[t]) cnt[t] += cnt[t*2+1];
    }
    void push(int t) {
        mn[t*2] += lz[t];
        mn[t*2+1] += lz[t];
        lz[t*2] += lz[t];
        lz[t*2+1] += lz[t];
        lz[t] = 0;
    }
    void upd(int ul, int ur, int v, int t, int l, int r) {
        if (ur <= l || r <= ul) return;
        if (ul <= l && r <= ur) {
            mn[t] += v;
            lz[t] += v;
            return;
        }
        push(t);
        int m = l+r>>1;
        upd(ul, ur, v, t*2, l, m);
        upd(ul, ur, v, t*2+1, m, r);
        pull(t);
    }
    void upd(int ul, int ur, int v) {upd(ul, ur, v, 1, 0, sz);}
} st;
 
void upd_sqr(int i, int j, int v) {
    vector<int> pts;
    for (int ni = 0; ni < 2; ++ni)
        for (int nj = 0; nj < 2; ++nj)
            pts.push_back(grid[i+ni][j+nj]);
    sort(pts.begin(), pts.end());
    st.upd(pts[0], pts[1], v);
    st.upd(pts[2], pts[3], v);
}
 
void upd_pt(int i, int j, int v) {
    for (auto& [di, dj] : (pair<int,int>[]){{0, 0}, {-1, 0}, {-1, -1}, {0, -1}}) {
        upd_sqr(i+di, j+dj, v);
    }
}
 
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    for (int i: R) r.push_back(i+1);
    for (int i: C) c.push_back(i+1);
    grid.assign(H+2, vector<int>(W+2, H*W));
    for (int i = 0; i < H*W; ++i) {
        grid[r[i]][c[i]] = i;
    }
    vector<int> d(H*W+1), vals(H*W);
    for (int i = 0; i <= H; ++i) {
        for (int j = 0; j <= W; ++j) {
            vector<int> pts;
            for (int ni = 0; ni < 2; ++ni)
                for (int nj = 0; nj < 2; ++nj)
                    pts.push_back(grid[i+ni][j+nj]);
            sort(pts.begin(), pts.end());
            d[pts[0]]++;
            d[pts[1]]--;
            d[pts[2]]++;
            d[pts[3]]--;
        }
    }
    int v = 0;
    for (int i = 0; i < H*W; ++i) {
        v += d[i];
        vals[i] = v;
    }
    st.build(vals, 0, H*W);
}
 
int swap_seats(int a, int b) {
    upd_pt(r[a], c[a], -1);
    upd_pt(r[b], c[b], -1);
    swap(grid[r[a]][c[a]], grid[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    upd_pt(r[a], c[a], 1);
    upd_pt(r[b], c[b], 1);
    return st.cnt[1];
}

Compilation message (stderr)

seats.cpp: In member function 'void LazyST::build(std::vector<int>&, int, int, int)':
seats.cpp:17:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |             int m = l+r>>1;
      |                     ~^~
seats.cpp: In member function 'void LazyST::upd(int, int, int, int, int, int)':
seats.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int m = l+r>>1;
      |                 ~^~
seats.cpp: In function 'void upd_pt(int, int, int)':
seats.cpp:63:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto& [di, dj] : (pair<int,int>[]){{0, 0}, {-1, 0}, {-1, -1}, {0, -1}}) {
      |                ^

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