Submission #1106688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106688		snpmrnhlol	Seats (IOI18_seats)	C++17	25 / 100	4064 ms	111984 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 15e2;
struct nod{
    int mn,mx;
}seg[2][4*N*N];
nod operator+(nod a, nod b){
    return {min(a.mn,b.mn),max(a.mx,b.mx)};
}
int sz;
void upd(int pos, int x, int y, int l = 0, int r = sz - 1, int node = 1){
    if(l == r){
        seg[0][node] = {x, x};
        seg[1][node] = {y, y};
    }else{
        int mij = (l + r)/2;
        if(pos <= mij){
            upd(pos, x, y, l, mij, node*2);
        }else{
            upd(pos, x, y, mij + 1, r, node*2 + 1);
        }
        seg[0][node] = seg[0][node*2] + seg[0][node*2 + 1];
        seg[1][node] = seg[1][node*2] + seg[1][node*2 + 1];
    }
}
nod query(int ql, int qr, int id, int l = 0, int r = sz - 1, int node = 1){
    if(r < ql || qr < l)return {sz, -1};
    if(ql <= l && r <= qr){
        return seg[id][node];
    }else{
        int mij = (l + r)/2;
        return query(ql, qr, id, l, mij, node*2) + query(ql, qr, id, mij + 1, r, node*2 + 1);
    }
}
std::vector<std::vector<int>> v;
vector <int> x,y;
int n,m;
void give_initial_chart(int n2, int m2, std::vector<int> a, std::vector<int> b) {
    n = n2;m = m2;
    v.assign(n, vector<int>(m,0));
    x = a;
    y = b;
    sz = n*m;
    for(int i = 0;i < n*m;i++){
        v[x[i]][y[i]] = i;
        upd(i, x[i], y[i]);
    }
}
int prevans = -1;
int swap_seats(int a, int b){
    if(a > b)swap(a,b);
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    upd(a, x[a], y[a]);
    upd(b, x[b], y[b]);
    swap(v[x[a]][y[a]],v[x[b]][y[b]]);
    int ans = 0;
    int ans2 = 0;
    int ans3 = 0;
    if(b - a <= 10000 && prevans != -1){
        ans3 = prevans;
        int r = -1,l = m,d = -1,u = n;
        nod p1 = query(0, a - 1, 0);
        nod p2 = query(0, a - 1, 1);
        l = min(p2.mn, y[b]);r = max(p2.mx, y[b]);
        u = min(p1.mn, x[b]);d = max(p1.mx, x[b]);
        if((r - l + 1)*(d - u + 1) == a + 1){
            ans3--;
        }
        for(int i = a + 1;i < b;i++){
            l  = min(l,y[i]);
            r  = max(r,y[i]);
            u  = min(u,x[i]);
            d  = max(d,x[i]);
            if((r - l + 1)*(d - u + 1) == i + 1){
                ans3--;
            }
        }
        l = p2.mn;r = p2.mx;
        u = p1.mn;d = p1.mx;
        for(int i = a;i < b;i++){
            l  = min(l,y[i]);
            r  = max(r,y[i]);
            u  = min(u,x[i]);
            d  = max(d,x[i]);
            if((r - l + 1)*(d - u + 1) == i + 1){
                ans3++;
            }
        }
        int i = 0;
        while(i < n*m){
            nod p1 = query(0, i, 0);
            nod p2 = query(0, i, 1);
            int matrixsz = (p1.mx - p1.mn + 1)*(p2.mx - p2.mn + 1);
            if(matrixsz == i + 1){
                ans++;
            }
            i = max(i + 1, matrixsz - 1);
        }
        assert(ans == ans3);
    }else if(n + m <= 2000){
        int i = 0;
        while(i < n*m){
            nod p1 = query(0, i, 0);
            nod p2 = query(0, i, 1);
            int matrixsz = (p1.mx - p1.mn + 1)*(p2.mx - p2.mn + 1);
            if(matrixsz == i + 1){
                ans++;
            }
            i = max(i + 1, matrixsz - 1);
        }
    }else if(n*m <= 10000){
        int r = -1,l = m,d = -1,u = n;
        for(int i = 0;i < n*m;i++){
            l  = min(l,y[i]);
            r  = max(r,y[i]);
            u  = min(u,x[i]);
            d  = max(d,x[i]);
            if((r - l + 1)*(d - u + 1) == i + 1){
                ans2++;
            }
        }
    }
    prevans = max({ans,ans2,ans3});
    return prevans;
}
/**
3 3 3
2 2
1 2
0 2
0 1
0 0
2 1
1 1
1 0
2 0

6 0
5 7
6 4
**/

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