Submission #1208845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208845		notme	Seats (IOI18_seats)	C++20	5 / 100	4094 ms	56900 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int maxn = 1e6 + 10;
int n, h, w;
int rw[maxn], cw[maxn];
struct node
{
    int minr, maxr, minc, maxc;
    node(){};
    node(int _minr, int _maxr, int _minc, int _maxc)
    {
        minr = _minr;
        maxr = _maxr;
        minc = _minc;
        maxc = _maxc;
    }
};
node t[maxn * 4];
node join(int i)
{
    return node(min(t[2*i].minr, t[2*i+1].minr), max(t[2*i].maxr, t[2*i+1].maxr), min(t[2*i].minc, t[2*i+1].minc), max(t[2*i].maxc, t[2*i+1].maxc));
}
void build(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = node(rw[l], rw[l], cw[l], cw[l]);
        return;
    }
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    t[i] = join(i);
}
int updpos;
void update(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = node(rw[l], rw[l], cw[l], cw[l]);
        return;
    }
    int mid = (l + r)/2;
    if(updpos <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = join(i);
}
int ql, qr;

pair < int, int > queryrow(int i, int l, int r)
{
    if(qr < l || ql > r)return make_pair(1e9, -1);
    if(ql <= l && r <= qr)return make_pair(t[i].minr, t[i].maxr);
    int mid = (l + r)/2;
    pair < int, int > fh = queryrow(2*i, l, mid);
    pair < int, int > sh = queryrow(2*i+1, mid+1, r);
    return make_pair(min(fh.first, sh.first), max(fh.second, sh.second));
}
pair < int, int > querycol(int i, int l, int r)
{
    if(qr < l || ql > r)return make_pair(1e9, -1);
    if(ql <= l && r <= qr)return make_pair(t[i].minc, t[i].maxc);
    int mid = (l + r)/2;
    pair < int, int > fh = querycol(2*i, l, mid);
    pair < int, int > sh = querycol(2*i+1, mid+1, r);
    return make_pair(min(fh.first, sh.first), max(fh.second, sh.second));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
  h = H;
  w = W;
  n = h * w;
  for (int i = 0; i < n; ++ i)
  {
      rw[i] = R[i];
      cw[i] = C[i];
  }
    build(1, 0, n-1);
//  cout << "ans ids " << ans << endl;

}

int swap_seats(int a, int b)
{
    swap(rw[a], rw[b]);
    swap(cw[a], cw[b]);
    updpos = a;
    update(1, 0, n-1);
    updpos = b;
    update(1, 0, n-1);
    int take = 0;
    int minr = rw[0];
    int maxr = rw[0];
    int minc = cw[0];
    int maxc = cw[0];
    int ans = 0;
    while(take < n)
    {
        //cout << take << endl;
        int sum = (maxr - minr + 1)*(maxc - minc + 1);
        if(sum == take + 1)
        {
            ans ++;
            take ++;
        }
        else
        {
            take = sum - 1;
        }
        if(take == n)break;
        ql = 0;
        qr = take;
        pair < int, int > rows = queryrow(1, 0, n-1);
        pair < int, int > cols = querycol(1, 0, n-1);
        minr = rows.first;
        maxr = rows.second;
        minc = cols.first;
        maxc = cols.second;
    }
    assert(ans < (h + w)*10);
    return ans;
}

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