답안 #85057 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
85057	2018-11-18T11:05:57 Z	nikolapesic2802	자리 배치 (IOI18_seats)	C++14	100 / 100	3844 ms	159816 KB

seats

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
int N;
struct segTree{
    vector<int> ones,tri;
    vector<int> sum;
    vector<pair<int,int> > minn;
    vector<int> num;
    void set(int i,int l,int r)
    {
        num[i]=r-l+1;
        if(l==r)
            return;
        int m=(l+r)>>1;
        set(2*i,l,m);
        set(2*i+1,m+1,r);
    }
    void init()
    {
        ones.resize(4*N);
        tri.resize(4*N);
        minn.resize(4*N);
        num.resize(4*N);
        set(1,0,N-1);
    }
    void prop(int i)
    {
        if(ones[i]!=0){
            ones[2*i]+=ones[i];
            minn[2*i].first+=ones[i];
            ones[2*i+1]+=ones[i];
            minn[2*i+1].first+=ones[i];
            ones[i]=0;
        }
        if(tri[i]!=0){
            tri[2*i]+=tri[i];
            minn[2*i].second+=tri[i];
            tri[2*i+1]+=tri[i];
            minn[2*i+1].second+=tri[i];
            tri[i]=0;
        }
    }
    void update(int i)
    {
        if(minn[2*i]==minn[2*i+1])
        {
            minn[i]=minn[2*i];
            num[i]=num[2*i]+num[2*i+1];
            return;
        }
        if(minn[2*i]<minn[2*i+1])
        {
            minn[i]=minn[2*i];
            num[i]=num[2*i];
            return;
        }
        if(minn[2*i]>minn[2*i+1])
        {
            minn[i]=minn[2*i+1];
            num[i]=num[2*i+1];
        }
    }
    void update_all(int i=1,int l=0,int r=N-1)
    {
        if(l==r){
            minn[i].first+=ones[i];
            minn[i].second+=tri[i];
            return;
        }
        int m=(l+r)>>1;
        ones[2*i]+=ones[i];
        ones[2*i+1]+=ones[i];
        ones[i]=0;
        tri[2*i]+=tri[i];
        tri[2*i+1]+=tri[i];
        tri[i]=0;
        update_all(2*i,l,m);
        update_all(2*i+1,m+1,r);
        update(i);
    }
    void no_updates(int qs,int qe,int x,int sta,int i=1,int l=0,int r=N-1)
    {
        if(qe<qs)
            return;
        if(r<qs||l>qe)
            return;
        if(qs<=l&&r<=qe)
        {
            if(sta==0){
                ones[i]+=x;
            }
            else{
                tri[i]+=x;
            }
            return;
        }
        int m=(l+r)>>1;
        no_updates(qs,qe,x,sta,2*i,l,m);
        no_updates(qs,qe,x,sta,2*i+1,m+1,r);
    }
    void add(int qs,int qe,int x,int sta,int i=1,int l=0,int r=N-1)
    {
        if(qe<qs)
            return;
        if(r<qs||l>qe)
            return;
        if(qs<=l&&r<=qe)
        {
            if(sta==0){
                ones[i]+=x;
                minn[i].first+=x;
            }
            else{
                tri[i]+=x;
                minn[i].second+=x;
            }
            return;
        }
        int m=(l+r)>>1;
        prop(i);
        add(qs,qe,x,sta,2*i,l,m);
        add(qs,qe,x,sta,2*i+1,m+1,r);
        update(i);
    }
    int get()
    {
        if(minn[1]==make_pair(4,0))
            return num[1];
        return 0;
    }
} ST;
vector<vector<int> > mat;
int h,w;
bool inside(int x,int y)
{
    if(x>=0&&x<h&&y>=0&&y<w)
        return true;
    return false;
}
void update(int x,int y,int z)
{
    vector<int> val;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            if(inside(x+i,y+j))
                val.pb(mat[x+i][y+j]);
            else
                val.pb(N);
        }
    sort(val.begin(),val.end());
    ST.add(val[0],val[1]-1,z,0);
    ST.add(val[2],val[3]-1,z,1);
}
void update2(int x,int y,int z)
{
    vector<int> val;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            if(inside(x+i,y+j))
                val.pb(mat[x+i][y+j]);
            else
                val.pb(N);
        }
    sort(val.begin(),val.end());
    ST.no_updates(val[0],val[1]-1,z,0);
    ST.no_updates(val[2],val[3]-1,z,1);
}
vector<int> r,c;
vector<bool> sol;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h=H;
    w=W;
    sol.resize(H*W);
    mat.resize(H);
    for(int i=0;i<H;i++)
        mat[i].resize(W);
    N=H*W;
    ST.init();
    for(int i=0;i<H*W;i++){
        mat[R[i]][C[i]]=i;
        r.pb(R[i]);
        c.pb(C[i]);
    }
    for(int i=-1;i<H;i++)
        for(int j=-1;j<W;j++)
            update2(i,j,1);
    ST.update_all();
}
int swap_seats(int a, int b) {
    for(int i=-1;i<=0;i++)
        for(int j=-1;j<=0;j++)
            update(r[a]+i,c[a]+j,-1);
    for(int i=-1;i<=0;i++)
        for(int j=-1;j<=0;j++)
            update(r[b]+i,c[b]+j,-1);
    swap(mat[r[a]][c[a]],mat[r[b]][c[b]]);
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    for(int i=-1;i<=0;i++)
        for(int j=-1;j<=0;j++)
            update(r[a]+i,c[a]+j,1);
    for(int i=-1;i<=0;i++)
        for(int j=-1;j<=0;j++)
            update(r[b]+i,c[b]+j,1);
    return ST.get();
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	504 KB	Output is correct
2	Correct	40 ms	748 KB	Output is correct
3	Correct	63 ms	748 KB	Output is correct
4	Correct	39 ms	752 KB	Output is correct
5	Correct	38 ms	756 KB	Output is correct
6	Correct	48 ms	828 KB	Output is correct
7	Correct	52 ms	912 KB	Output is correct
8	Correct	49 ms	912 KB	Output is correct
9	Correct	64 ms	976 KB	Output is correct
10	Correct	56 ms	1112 KB	Output is correct
11	Correct	65 ms	1112 KB	Output is correct
12	Correct	37 ms	1112 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	504 KB	Output is correct
2	Correct	40 ms	748 KB	Output is correct
3	Correct	63 ms	748 KB	Output is correct
4	Correct	39 ms	752 KB	Output is correct
5	Correct	38 ms	756 KB	Output is correct
6	Correct	48 ms	828 KB	Output is correct
7	Correct	52 ms	912 KB	Output is correct
8	Correct	49 ms	912 KB	Output is correct
9	Correct	64 ms	976 KB	Output is correct
10	Correct	56 ms	1112 KB	Output is correct
11	Correct	65 ms	1112 KB	Output is correct
12	Correct	37 ms	1112 KB	Output is correct
13	Correct	116 ms	2068 KB	Output is correct
14	Correct	129 ms	2068 KB	Output is correct
15	Correct	71 ms	2068 KB	Output is correct
16	Correct	53 ms	2528 KB	Output is correct
17	Correct	98 ms	2528 KB	Output is correct
18	Correct	90 ms	2528 KB	Output is correct
19	Correct	82 ms	2528 KB	Output is correct
20	Correct	76 ms	2528 KB	Output is correct
21	Correct	55 ms	2528 KB	Output is correct
22	Correct	71 ms	2528 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2015 ms	108076 KB	Output is correct
2	Correct	1209 ms	108096 KB	Output is correct
3	Correct	1117 ms	108532 KB	Output is correct
4	Correct	1014 ms	108556 KB	Output is correct
5	Correct	1049 ms	108672 KB	Output is correct
6	Correct	983 ms	108672 KB	Output is correct
7	Correct	1076 ms	108672 KB	Output is correct
8	Correct	1192 ms	108800 KB	Output is correct
9	Correct	1127 ms	108800 KB	Output is correct
10	Correct	1139 ms	108800 KB	Output is correct

Subtask #4
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	106 ms	108800 KB	Output is correct
2	Correct	207 ms	108800 KB	Output is correct
3	Correct	1025 ms	108800 KB	Output is correct
4	Correct	1997 ms	109064 KB	Output is correct
5	Correct	1218 ms	109064 KB	Output is correct
6	Correct	2135 ms	159816 KB	Output is correct
7	Correct	1044 ms	159816 KB	Output is correct
8	Correct	1211 ms	159816 KB	Output is correct
9	Correct	1129 ms	159816 KB	Output is correct
10	Correct	1144 ms	159816 KB	Output is correct
11	Correct	1266 ms	159816 KB	Output is correct

Subtask #5
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	187 ms	159816 KB	Output is correct
2	Correct	244 ms	159816 KB	Output is correct
3	Correct	425 ms	159816 KB	Output is correct
4	Correct	383 ms	159816 KB	Output is correct
5	Correct	545 ms	159816 KB	Output is correct
6	Correct	1917 ms	159816 KB	Output is correct
7	Correct	1990 ms	159816 KB	Output is correct
8	Correct	1775 ms	159816 KB	Output is correct
9	Correct	2930 ms	159816 KB	Output is correct
10	Correct	1699 ms	159816 KB	Output is correct
11	Correct	1633 ms	159816 KB	Output is correct
12	Correct	1616 ms	159816 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	504 KB	Output is correct
2	Correct	40 ms	748 KB	Output is correct
3	Correct	63 ms	748 KB	Output is correct
4	Correct	39 ms	752 KB	Output is correct
5	Correct	38 ms	756 KB	Output is correct
6	Correct	48 ms	828 KB	Output is correct
7	Correct	52 ms	912 KB	Output is correct
8	Correct	49 ms	912 KB	Output is correct
9	Correct	64 ms	976 KB	Output is correct
10	Correct	56 ms	1112 KB	Output is correct
11	Correct	65 ms	1112 KB	Output is correct
12	Correct	37 ms	1112 KB	Output is correct
13	Correct	116 ms	2068 KB	Output is correct
14	Correct	129 ms	2068 KB	Output is correct
15	Correct	71 ms	2068 KB	Output is correct
16	Correct	53 ms	2528 KB	Output is correct
17	Correct	98 ms	2528 KB	Output is correct
18	Correct	90 ms	2528 KB	Output is correct
19	Correct	82 ms	2528 KB	Output is correct
20	Correct	76 ms	2528 KB	Output is correct
21	Correct	55 ms	2528 KB	Output is correct
22	Correct	71 ms	2528 KB	Output is correct
23	Correct	2015 ms	108076 KB	Output is correct
24	Correct	1209 ms	108096 KB	Output is correct
25	Correct	1117 ms	108532 KB	Output is correct
26	Correct	1014 ms	108556 KB	Output is correct
27	Correct	1049 ms	108672 KB	Output is correct
28	Correct	983 ms	108672 KB	Output is correct
29	Correct	1076 ms	108672 KB	Output is correct
30	Correct	1192 ms	108800 KB	Output is correct
31	Correct	1127 ms	108800 KB	Output is correct
32	Correct	1139 ms	108800 KB	Output is correct
33	Correct	106 ms	108800 KB	Output is correct
34	Correct	207 ms	108800 KB	Output is correct
35	Correct	1025 ms	108800 KB	Output is correct
36	Correct	1997 ms	109064 KB	Output is correct
37	Correct	1218 ms	109064 KB	Output is correct
38	Correct	2135 ms	159816 KB	Output is correct
39	Correct	1044 ms	159816 KB	Output is correct
40	Correct	1211 ms	159816 KB	Output is correct
41	Correct	1129 ms	159816 KB	Output is correct
42	Correct	1144 ms	159816 KB	Output is correct
43	Correct	1266 ms	159816 KB	Output is correct
44	Correct	187 ms	159816 KB	Output is correct
45	Correct	244 ms	159816 KB	Output is correct
46	Correct	425 ms	159816 KB	Output is correct
47	Correct	383 ms	159816 KB	Output is correct
48	Correct	545 ms	159816 KB	Output is correct
49	Correct	1917 ms	159816 KB	Output is correct
50	Correct	1990 ms	159816 KB	Output is correct
51	Correct	1775 ms	159816 KB	Output is correct
52	Correct	2930 ms	159816 KB	Output is correct
53	Correct	1699 ms	159816 KB	Output is correct
54	Correct	1633 ms	159816 KB	Output is correct
55	Correct	1616 ms	159816 KB	Output is correct
56	Correct	280 ms	159816 KB	Output is correct
57	Correct	538 ms	159816 KB	Output is correct
58	Correct	810 ms	159816 KB	Output is correct
59	Correct	2395 ms	159816 KB	Output is correct
60	Correct	3844 ms	159816 KB	Output is correct
61	Correct	2076 ms	159816 KB	Output is correct
62	Correct	1836 ms	159816 KB	Output is correct
63	Correct	3641 ms	159816 KB	Output is correct
64	Correct	2492 ms	159816 KB	Output is correct
65	Correct	2067 ms	159816 KB	Output is correct
66	Correct	2430 ms	159816 KB	Output is correct
67	Correct	2431 ms	159816 KB	Output is correct
68	Correct	1895 ms	159816 KB	Output is correct
69	Correct	3736 ms	159816 KB	Output is correct

답안 #85057

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 6.0 / 6.0

Subtask #3 20.0 / 20.0

Subtask #4 6.0 / 6.0

Subtask #5 33.0 / 33.0

Subtask #6 30.0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
6.0 / 6.0

Subtask #3
20.0 / 20.0

Subtask #4
6.0 / 6.0

Subtask #5
33.0 / 33.0

Subtask #6
30.0 / 30.0