Submission #1164856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164856		Hanksburger	Seats (IOI18_seats)	C++17	100 / 100	2290 ms	103312 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> seg[4000005];
vector<vector<int> > rect;
int lazy[4000005], n, m;
vector<int> a, b;
pair<int, int> combine(pair<int, int> x, pair<int, int> y)
{
    if (x.first<y.first)
        return x;
    if (x.first>y.first)
        return y;
    return {x.first, x.second+y.second};
}
void push(int i, int l, int r)
{
    if (l<r)
    {
        seg[i*2].first+=lazy[i];
        seg[i*2+1].first+=lazy[i];
        lazy[i*2]+=lazy[i];
        lazy[i*2+1]+=lazy[i];
    }
    lazy[i]=0;
}
void build(int i, int l, int r)
{
    if (l==r)
    {
        seg[i]={0, 1};
        return;
    }
    int mid=(l+r)/2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    seg[i]=combine(seg[i*2], seg[i*2+1]);
}
void upd(int i, int l, int r, int ql, int qr, int val)
{
    if (ql<=l && r<=qr)
    {
        seg[i].first+=val;
        lazy[i]+=val;
        return;
    }
    push(i, l, r);
    int mid=(l+r)/2;
    if (l<=qr && ql<=mid)
        upd(i*2, l, mid, ql, qr, val);
    if (mid<qr && ql<=r)
        upd(i*2+1, mid+1, r, ql, qr, val);
    seg[i]=combine(seg[i*2], seg[i*2+1]);
}
pair<int, int> qry(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return seg[i];
    push(i, l, r);
    int mid=(l+r)/2;
    pair<int, int> res={1e9, 1};
    if (l<=qr && ql<=mid)
        res=combine(res, qry(i*2, l, mid, ql, qr));
    if (mid<qr && ql<=r)
        res=combine(res, qry(i*2+1, mid+1, r, ql, qr));
    return res;
}
void update(int x, int y, int val)
{
    //cout << "update " << x << ' ' << y << ' ' << "val: ";
    vector<int> tmp;
    tmp.push_back(x==0?n*m:(y==0?n*m:rect[x-1][y-1]));
    tmp.push_back(x==0?n*m:(y==m?n*m:rect[x-1][y]));
    tmp.push_back(x==n?n*m:(y==0?n*m:rect[x][y-1]));
    tmp.push_back(x==n?n*m:(y==m?n*m:rect[x][y]));
    sort(tmp.begin(), tmp.end());
    //cout << tmp[0] << ' ' << tmp[1] << ' ' << tmp[2] << ' ' << tmp[3] << '\n';
    if (tmp[0]<tmp[1])
        upd(1, 0, n*m, tmp[0], tmp[1]-1, val);
    if (tmp[2]<tmp[3])
        upd(1, 0, n*m, tmp[2], tmp[3]-1, val);
}
void give_initial_chart(int N, int M, vector<int> A, vector<int> B)
{
    n=N, m=M, a=A, b=B;
    for (int i=0; i<n; i++)
    {
        vector<int> tmp(m);
        rect.push_back(tmp);
    }
    for (int i=0; i<n*m; i++)
        rect[a[i]][b[i]]=i;
    build(1, 0, n*m);
    for (int i=0; i<=n; i++)
        for (int j=0; j<=m; j++)
            update(i, j, 1);
    //for (int i=0; i<=n*m; i++)
    //    cout << qry(1, 0, n*m, i, i).first << ' ';
    //cout << '\n';
}
int swap_seats(int x, int y)
{
    int xa=a[x], xb=b[x], ya=a[y], yb=b[y];
    vector<pair<int, int> > tmp;
    tmp.push_back({xa, xb});
    tmp.push_back({xa, xb+1});
    tmp.push_back({xa+1, xb});
    tmp.push_back({xa+1, xb+1});
    tmp.push_back({ya, yb});
    tmp.push_back({ya, yb+1});
    tmp.push_back({ya+1, yb});
    tmp.push_back({ya+1, yb+1});
    sort(tmp.begin(), tmp.end());
    tmp.resize(unique(tmp.begin(), tmp.end())-tmp.begin());
    for (pair<int, int> p:tmp)
        update(p.first, p.second, -1);
    //for (int i=0; i<=n*m; i++)
    //    cout << qry(1, 0, n*m, i, i).first << ' ';
    //cout << '\n';
    rect[xa][xb]=y;
    rect[ya][yb]=x;
    for (pair<int, int> p:tmp)
        update(p.first, p.second, 1);
    a[x]=ya, b[x]=yb, a[y]=xa, b[y]=xb;
    //for (int i=0; i<=n*m; i++)
    //    cout << qry(1, 0, n*m, i, i).first << ' ';
    //cout << '\n';
    return qry(1, 0, n*m, 0, n*m-1).second;
}

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