제출 #788906

#제출 시각아이디문제언어결과실행 시간메모리
788906lukameladze자리 배치 (IOI18_seats)C++17
70 / 100
4086 ms135628 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <int, int> #define pb push_back const int N = 1e6 + 5, inf = 1e9; int r[N], c[N],all; int n,m; vector <vector <int> > a; // map ? struct nod { int mnf, mns, cnt; }; nod tree[4 * N]; int lazy[2][4 * N]; nod merge(nod a, nod b) { if (a.mnf != b.mnf) { return (a.mnf < b.mnf ? a : b); } if (a.mns != b.mns) { return (a.mns < b.mns ? a : b); } return {a.mnf, a.mns, a.cnt + b.cnt}; } void build(int node, int le, int ri) { if (le == ri) { tree[node] = {0, 0, 1}; return ; } int mid = (le + ri) / 2; build(2 * node, le, mid); build(2 * node + 1, mid + 1, ri); tree[node] = merge(tree[2 * node], tree[2 * node + 1]); } void push(int node, int le, int ri) { if (!lazy[0][node] && !lazy[1][node]) return ; tree[node].mnf += lazy[0][node]; tree[node].mns += lazy[1][node]; if (le != ri) { for (int ty = 0; ty < 2; ty++) { lazy[ty][2 * node] += lazy[ty][node]; lazy[ty][2 * node + 1] += lazy[ty][node]; } } lazy[0][node] = lazy[1][node] = 0; } void update(int node, int le, int ri, int start, int end, int val, int ty) { push(node, le, ri); if (le > end || ri < start) return ; if (le >= start && ri <= end) { lazy[ty][node] = val; push(node, le, ri); return ; } int mid = (le + ri) >> 1; update(2 * node, le, mid,start, end, val, ty); update(2 * node + 1, mid + 1, ri, start, end, val, ty); tree[node] = merge(tree[2 * node], tree[2 * node + 1]); } nod getans(int node, int le, int ri, int start, int end) { push(node, le, ri); if (le > end || ri < start) return {inf, inf, 0}; if (le >= start && ri <= end) { return tree[node]; } int mid = (le + ri) >> 1; return merge(getans(2 * node, le, mid, start, end), getans(2 * node + 1, mid + 1, ri, start, end)); } void upd(int l, int r, int vl, int ty) { update(1, 1, all, l, r, vl, ty); } void add(int i, int j, int vl) { vector <int> vec; vec.pb(a[i][j]); vec.pb(a[i + 1][j]); vec.pb(a[i][j + 1]); vec.pb(a[i + 1][j + 1]); sort(vec.begin(), vec.end()); if (vec[0] < vec[1]) upd(vec[0], vec[1] - 1, vl, 0); if (vec[2] < vec[3]) upd(vec[2], vec[3] - 1, vl, 1); } void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { n = H; m = W; a = vector < vector <int> > (n + 5, vector <int> (m + 5, 0)); for (int i = 0; i <= n + 1; i++) { for (int j = 0; j <= m + 1; j++) { a[i][j] = n * m + 1; } } all = n * m; for (int i = 0; i < n * m; i++) { r[i + 1] = R[i] + 1; c[i + 1] = C[i] + 1; a[r[i + 1]][c[i + 1]] = i + 1; } build(1, 1, all); for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { // {i, j} {i + 1, j} {i, j + 1} {i + 1, j + 1} add(i, j, 1); } } // for (int i = 1; i <= n * m; i++) { // cout<<i<<" -> "<<getans(1, 1, all, i, i).mnf<<" "<<getans(1 ,1, all, i, i).mns<<" "<<getans(1, 1, all, i, i).cnt<<"\n"; // } // cout<<tree[1].mnf<<" "<<tree[1].mns<<"\n"; // if (tree[1].mnf == 4 && tree[1].mns == 0) { // cout<<tree[1].cnt<<"\n"; // } } int swap_seats(int x, int y) { // {r[x], c[x]} --- > x++; y++; // cout<<"was "<<tree[1].mnf<<" "<<tree[1].mns<<"\n"; for (int ii = 0; ii < 2; ii++) { int pos = (ii == 0 ? x : y); for (int i = r[pos] - 1; i <= r[pos]; i++) { for (int j = c[pos] - 1; j <= c[pos]; j++) { add(i, j, -1); } } } a[r[x]][c[x]] = y; a[r[y]][c[y]] = x; swap(r[x], r[y]); swap(c[x], c[y]); for (int ii = 0; ii < 2; ii++) { int pos = (ii == 0 ? x : y); for (int i = r[pos] - 1; i <= r[pos]; i++) { for (int j = c[pos] - 1; j <= c[pos]; j++) { add(i, j, 1); } } } if (tree[1].mnf == 4 && tree[1].mns == 0) { return tree[1].cnt; } else return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...