Submission #161808

#	Time	Username	Problem	Language	Result	Execution time	Memory
161808		mhy908	Seats (IOI18_seats)	C++14	0 / 100	1851 ms	182300 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
void ADD(pii &a, pii b){
    a.F+=b.F;
    a.S+=b.S;
}
struct SEGMENT_TREE{
    struct NODE{
        int st, fin, minnum;
        pii minn, lazy;
    }tree[4000010];
    int x;
    void maketree(int point, int num) {
        if(num==1){
            tree[point].st=tree[point].fin=++x;
            tree[point].minnum=1;
        }
        if(num<=1)return;
        maketree(point*2, num-num/2);
        maketree(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void propogate(int point){
        ADD(tree[2*point].minn, tree[point].lazy);
        ADD(tree[2*point+1].minn, tree[point].lazy);
        ADD(tree[2*point].lazy, tree[point].lazy);
        ADD(tree[2*point+1].lazy, tree[point].lazy);
        tree[point].lazy=pii(0, 0);
    }
    void relaxnode(int point){
        if(tree[point].st==tree[point].fin)return;
        tree[point].minn=min(tree[point*2].minn, tree[point*2+1].minn);
        tree[point].minnum=0;
        if(tree[point].minn==tree[point*2].minn)tree[point].minnum+=tree[point*2].minnum;
        if(tree[point].minn==tree[point*2+1].minn)tree[point].minnum+=tree[point*2+1].minnum;
    }
    void alterrange(int point, int a, int b, pii p) {
        if(tree[point].fin<a||tree[point].st>b)return;
        if(tree[point].st>=a&&tree[point].fin<=b) {
            ADD(tree[point].minn, p);
            ADD(tree[point].lazy, p);
            return;
        }
        propogate(point);
        alterrange(point*2, a, b, p);
        alterrange(point*2+1, a, b, p);
        relaxnode(point);
    }
    void print(int point){
        printf("%d ~ %d : minn-(%d %d), lazy-(%d %d), minnum-%d\n", tree[point].st, tree[point].fin, tree[point].minn.F, tree[point].minn.S, tree[point].lazy.F, tree[point].lazy.S, tree[point].minnum);
        if(tree[point].st!=tree[point].fin)print(point*2), print(point*2+1);
    }
    int query(){
        return tree[1].minn==pii(4, 0)?tree[1].minnum:0;
    }
}seg;
vector<vector<int> > grid;
vector<vector<int> > valid;
vector<int> r, c, upd;
int n, m;
pii temp[1000010];
void print()
{
    puts("====");
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            printf("%d ", grid[i][j]);
        }
        puts("");
    }
    puts("====");
}
void updateall()
{
    sort(all(upd));
    upd.resize(unique(all(upd))-upd.begin());
    pii t=pii(0, 0);
    for(int i=0; i<upd.size()-1; i++){
        ADD(t, temp[upd[i]]);
        seg.alterrange(1, upd[i]+1, upd[i+1], t);
    }
    for(int i=0; i<upd.size(); i++)temp[i]=pii(0, 0);
    upd.clear();
    //seg.print(1);
}
void update(int x, int y, int p)
{
    if((valid[x][y]==0&&p==-1)||(valid[x][y]==1&&p==1))return;
    valid[x][y]^=1;
    vector<pii> tem;
    tem.pb(mp(grid[x][y], 0));
    tem.pb(mp(grid[x+1][y], 1));
    tem.pb(mp(grid[x+1][y+1], 2));
    tem.pb(mp(grid[x][y+1], 3));
    sort(all(tem));
    for(int i=0; i<3; i++){
        int st=tem[i].F, fin=tem[i+1].F;
        st=max(st, 0);
        fin=min(fin, n*m);
        if(st>=fin)continue;
        pii up;
        if(i==0)up=pii(p, 0);
        if(i==1){
            if((tem[0].S^tem[1].S)==2)up=pii(2*p, 0);
            else continue;
        }
        if(i==2)up=pii(0, p);
        ADD(temp[st], up);
        ADD(temp[fin], mp(-up.F, -up.S));
        upd.pb(st);
        upd.pb(fin);
    }
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n=H;
    m=W;
    r=R;
    c=C;
    grid.resize(n+2);
    valid.resize(n+1);
    for(int i=0; i<grid.size(); i++)grid[i].resize(m+2);
    for(int i=0; i<valid.size(); i++)valid[i].resize(m+1);
    for(int i=0; i<grid.size(); i++)
        for(int j=0; j<grid[i].size(); j++)
            grid[i][j]=10000000;
    for(int i=0; i<n*m; i++){
        grid[r[i]+1][c[i]+1]=i;
    }
    seg.maketree(1, n*m);
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            update(i, j, 1);
        }
    }
    //print();
}
int swap_seats(int a, int b){
    for(int i=0; i<=1; i++){
        for(int j=0; j<=1; j++){
            update(r[a]+i, c[a]+j, -1);
            update(r[b]+i, c[b]+j, -1);
        }
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    swap(grid[r[a]+1][c[a]+1], grid[r[b]+1][c[b]+1]);
    for(int i=0; i<=1; i++){
        for(int j=0; j<=1; j++){
            update(r[a]+i, c[a]+j, 1);
            update(r[b]+i, c[b]+j, 1);
        }
    }
    //print();
    updateall();
    return seg.query();
}
/*
2 3 2
0 0 1 0 1 1 0 1 0 2 1 2
0 5
0 5
*/

Compilation message (stderr)

seats.cpp: In function 'void updateall()':
seats.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<upd.size()-1; i++){
                  ~^~~~~~~~~~~~~
seats.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<upd.size(); i++)temp[i]=pii(0, 0);
                  ~^~~~~~~~~~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grid.size(); i++)grid[i].resize(m+2);
                  ~^~~~~~~~~~~~
seats.cpp:131:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<valid.size(); i++)valid[i].resize(m+1);
                  ~^~~~~~~~~~~~~
seats.cpp:132:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grid.size(); i++)
                  ~^~~~~~~~~~~~
seats.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<grid[i].size(); j++)
                      ~^~~~~~~~~~~~~~~

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