oj.uz

답안 #930095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930095 2024-02-18T13:12:46 Z HuyQuang_re_Zero 자리 배치 (IOI18_seats) C++14
100 / 100
 3031 ms 140112 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "seats.h"
struct pt
{
    int mi3,mi1,slmi;
    friend pt operator + (pt a,pt b)
    {
        if(a.mi3<b.mi3) return a;
        if(b.mi3<a.mi3) return b;
        if(a.mi1<b.mi1) return a;
        if(b.mi1<a.mi1) return b;
        return { a.mi3,a.mi1,a.slmi+b.slmi };
    }
};
struct Interval_Tree
{
    pt st[4*maxn];
    int lz3[4*maxn],lz1[4*maxn];
    void change(int id,int k3,int k1)
    {
        st[id].mi3+=k3;
        st[id].mi1+=k1;
        lz3[id]+=k3;
        lz1[id]+=k1;
    }
    void down(int id)
    {
        change(id*2,lz3[id],lz1[id]);
        change(id*2+1,lz3[id],lz1[id]);
        lz3[id]=lz1[id]=0;
    }
    void build(int id,int l,int r)
    {
        if(l==r) { st[id]={ 0,0,1 }; return ; }
        int mid=(l+r)>>1;
        build(id*2,l,mid); build(id*2+1,mid+1,r);
        st[id]=st[id*2]+st[id*2+1];
    }
    void update(int id,int l,int r,int u,int v,int k3,int k1)
    {
        if(u>r || v<l) return ;
        if(u<=l && r<=v) { change(id,k3,k1); return ; }
        down(id);
        int mid=(l+r)>>1;
        update(id*2,l,mid,u,v,k3,k1); update(id*2+1,mid+1,r,u,v,k3,k1);
        st[id]=st[id*2]+st[id*2+1];
    }
} IT;

vector <int> a[maxn];
int n,m,x[maxn],y[maxn],i,j;
void Work(int x,int y,int k)
{
    if(a[x][y]==-1 || a[x][y+1]==-1 || a[x+1][y]==-1 || a[x+1][y+1]==-1) return ;
    vector <int> vec;
    vec.push_back(a[x][y]);
    vec.push_back(a[x][y+1]);
    vec.push_back(a[x+1][y]);
    vec.push_back(a[x+1][y+1]);
    sort(vec.begin(),vec.end());
    IT.update(1,1,n*m,vec[0],vec[1]-1,0,k);
    IT.update(1,1,n*m,vec[2],vec[3]-1,k,0);
}
void give_initial_chart(int _n,int _m,vector <int> _X,vector <int> _Y)
{
    n=_n; m=_m;
    for(i=0;i<n*m;i++) x[i+1]=_X[i]+1,y[i+1]=_Y[i]+1;
    for(i=0;i<=n+1;i++) a[i].resize(m+2);
    for(i=1;i<=n*m;i++) a[x[i]][y[i]]=i;
    for(i=0;i<=m+1;i++) a[0][i]=a[n+1][i]=n*m+1;
    for(i=1;i<=n;i++) a[i][0]=a[i][m+1]=n*m+1;

    IT.build(1,1,n*m);
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++) Work(i,j,1);
}


int swap_seats(int u,int v)
{
    u++; v++;
    Work(x[u]-1,y[u]-1,-1);
    Work(x[u]-1,y[u],-1);
    Work(x[u],y[u]-1,-1);
    Work(x[u],y[u],-1);
    a[x[u]][y[u]]=-1;
    Work(x[v]-1,y[v]-1,-1);
    Work(x[v]-1,y[v],-1);
    Work(x[v],y[v]-1,-1);
    Work(x[v],y[v],-1);
    a[x[v]][y[v]]=-1;

    swap(x[u],x[v]);
    swap(y[u],y[v]);
    a[x[u]][y[u]]=u;
    Work(x[u]-1,y[u]-1,1);
    Work(x[u]-1,y[u],1);
    Work(x[u],y[u]-1,1);
    Work(x[u],y[u],1);

    a[x[v]][y[v]]=v;
    Work(x[v]-1,y[v]-1,1);
    Work(x[v]-1,y[v],1);
    Work(x[v],y[v]-1,1);
    Work(x[v],y[v],1);

    return IT.st[1].slmi;
}

/*
int main()
{
    freopen("seats.inp","r",stdin);
    freopen("seats.out","w",stdout);
    int n,m,q,i,x,y,k;
    vector <int> X,Y;
    cin>>n>>m>>q;
    for(i=1;i<=n*m;i++) cin>>x>>y,X.push_back(x),Y.push_back(y);
    give_initial_chart(n,m,X,Y);
    for(i=1;i<=q;i++) cin>>x>>y,cout<<swap_seats(x,y)<<'\n';
}
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 29312 KB Output is correct
2 Correct 25 ms 29272 KB Output is correct
3 Correct 34 ms 29276 KB Output is correct
4 Correct 24 ms 29316 KB Output is correct
5 Correct 22 ms 29312 KB Output is correct
6 Correct 31 ms 29276 KB Output is correct
7 Correct 32 ms 29276 KB Output is correct
8 Correct 38 ms 29292 KB Output is correct
9 Correct 30 ms 29272 KB Output is correct
10 Correct 32 ms 29272 KB Output is correct
11 Correct 34 ms 29300 KB Output is correct
12 Correct 23 ms 29272 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 29312 KB Output is correct
2 Correct 25 ms 29272 KB Output is correct
3 Correct 34 ms 29276 KB Output is correct
4 Correct 24 ms 29316 KB Output is correct
5 Correct 22 ms 29312 KB Output is correct
6 Correct 31 ms 29276 KB Output is correct
7 Correct 32 ms 29276 KB Output is correct
8 Correct 38 ms 29292 KB Output is correct
9 Correct 30 ms 29272 KB Output is correct
10 Correct 32 ms 29272 KB Output is correct
11 Correct 34 ms 29300 KB Output is correct
12 Correct 23 ms 29272 KB Output is correct
13 Correct 65 ms 29872 KB Output is correct
14 Correct 75 ms 29784 KB Output is correct
15 Correct 48 ms 30216 KB Output is correct
16 Correct 41 ms 30040 KB Output is correct
17 Correct 63 ms 29788 KB Output is correct
18 Correct 56 ms 29692 KB Output is correct
19 Correct 53 ms 29984 KB Output is correct
20 Correct 47 ms 30008 KB Output is correct
21 Correct 38 ms 29952 KB Output is correct
22 Correct 43 ms 30300 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1638 ms 112740 KB Output is correct
2 Correct 902 ms 112856 KB Output is correct
3 Correct 888 ms 112616 KB Output is correct
4 Correct 784 ms 112492 KB Output is correct
5 Correct 820 ms 112504 KB Output is correct
6 Correct 801 ms 112464 KB Output is correct
7 Correct 829 ms 112616 KB Output is correct
8 Correct 874 ms 112616 KB Output is correct
9 Correct 922 ms 112616 KB Output is correct
10 Correct 846 ms 112620 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 29784 KB Output is correct
2 Correct 145 ms 40104 KB Output is correct
3 Correct 815 ms 112612 KB Output is correct
4 Correct 1808 ms 112620 KB Output is correct
5 Correct 806 ms 120404 KB Output is correct
6 Correct 1675 ms 140112 KB Output is correct
7 Correct 827 ms 115320 KB Output is correct
8 Correct 1056 ms 112724 KB Output is correct
9 Correct 874 ms 112804 KB Output is correct
10 Correct 948 ms 114704 KB Output is correct
11 Correct 883 ms 124188 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 30836 KB Output is correct
2 Correct 124 ms 30892 KB Output is correct
3 Correct 171 ms 30672 KB Output is correct
4 Correct 220 ms 30928 KB Output is correct
5 Correct 330 ms 31436 KB Output is correct
6 Correct 1333 ms 121360 KB Output is correct
7 Correct 1548 ms 121388 KB Output is correct
8 Correct 1278 ms 121316 KB Output is correct
9 Correct 2479 ms 121580 KB Output is correct
10 Correct 1209 ms 121168 KB Output is correct
11 Correct 1204 ms 121424 KB Output is correct
12 Correct 1158 ms 121264 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 29312 KB Output is correct
2 Correct 25 ms 29272 KB Output is correct
3 Correct 34 ms 29276 KB Output is correct
4 Correct 24 ms 29316 KB Output is correct
5 Correct 22 ms 29312 KB Output is correct
6 Correct 31 ms 29276 KB Output is correct
7 Correct 32 ms 29276 KB Output is correct
8 Correct 38 ms 29292 KB Output is correct
9 Correct 30 ms 29272 KB Output is correct
10 Correct 32 ms 29272 KB Output is correct
11 Correct 34 ms 29300 KB Output is correct
12 Correct 23 ms 29272 KB Output is correct
13 Correct 65 ms 29872 KB Output is correct
14 Correct 75 ms 29784 KB Output is correct
15 Correct 48 ms 30216 KB Output is correct
16 Correct 41 ms 30040 KB Output is correct
17 Correct 63 ms 29788 KB Output is correct
18 Correct 56 ms 29692 KB Output is correct
19 Correct 53 ms 29984 KB Output is correct
20 Correct 47 ms 30008 KB Output is correct
21 Correct 38 ms 29952 KB Output is correct
22 Correct 43 ms 30300 KB Output is correct
23 Correct 1638 ms 112740 KB Output is correct
24 Correct 902 ms 112856 KB Output is correct
25 Correct 888 ms 112616 KB Output is correct
26 Correct 784 ms 112492 KB Output is correct
27 Correct 820 ms 112504 KB Output is correct
28 Correct 801 ms 112464 KB Output is correct
29 Correct 829 ms 112616 KB Output is correct
30 Correct 874 ms 112616 KB Output is correct
31 Correct 922 ms 112616 KB Output is correct
32 Correct 846 ms 112620 KB Output is correct
33 Correct 66 ms 29784 KB Output is correct
34 Correct 145 ms 40104 KB Output is correct
35 Correct 815 ms 112612 KB Output is correct
36 Correct 1808 ms 112620 KB Output is correct
37 Correct 806 ms 120404 KB Output is correct
38 Correct 1675 ms 140112 KB Output is correct
39 Correct 827 ms 115320 KB Output is correct
40 Correct 1056 ms 112724 KB Output is correct
41 Correct 874 ms 112804 KB Output is correct
42 Correct 948 ms 114704 KB Output is correct
43 Correct 883 ms 124188 KB Output is correct
44 Correct 111 ms 30836 KB Output is correct
45 Correct 124 ms 30892 KB Output is correct
46 Correct 171 ms 30672 KB Output is correct
47 Correct 220 ms 30928 KB Output is correct
48 Correct 330 ms 31436 KB Output is correct
49 Correct 1333 ms 121360 KB Output is correct
50 Correct 1548 ms 121388 KB Output is correct
51 Correct 1278 ms 121316 KB Output is correct
52 Correct 2479 ms 121580 KB Output is correct
53 Correct 1209 ms 121168 KB Output is correct
54 Correct 1204 ms 121424 KB Output is correct
55 Correct 1158 ms 121264 KB Output is correct
56 Correct 138 ms 30668 KB Output is correct
57 Correct 285 ms 30656 KB Output is correct
58 Correct 471 ms 31544 KB Output is correct
59 Correct 1636 ms 113528 KB Output is correct
60 Correct 2835 ms 113396 KB Output is correct
61 Correct 1473 ms 113748 KB Output is correct
62 Correct 1303 ms 117228 KB Output is correct
63 Correct 3031 ms 116172 KB Output is correct
64 Correct 1903 ms 114388 KB Output is correct
65 Correct 1766 ms 113632 KB Output is correct
66 Correct 1772 ms 113680 KB Output is correct
67 Correct 1702 ms 115908 KB Output is correct
68 Correct 1353 ms 120036 KB Output is correct
69 Correct 2540 ms 125296 KB Output is correct