Submission #639264

#	Time	Username	Problem	Language	Result	Execution time	Memory
639264		puppy	Untitled (POI11_rot)	C++17	63 / 100	414 ms	15272 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int g[400005][2], N;
int s[400005], e[400005];
int arr[400005];

struct sumseg
{
    int sz;
    vector<int> tree;
    void reset(int siz){sz = siz; tree.resize(1<<((int)ceil(log2(siz))+1));}
    int init(int s, int e, int node, vector<int> &arr)
    {
        if(s==e) return tree[node] = arr[s];
        return tree[node] = init(s, (s+e)/2, 2*node, arr) + init((s+e)/2+1, e, 2*node+1, arr);
    }
    void upd(int s, int e, int node, int idx, int val)
    {
        if(e<idx||idx<s) return;
        if(s==e){
            tree[node] += val; return;
        }
        upd(s, (s+e)/2, 2*node, idx, val); upd((s+e)/2+1, e, 2*node+1, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    int query(int s, int e, int node, int l, int r)
    {
        if(e<l||r<s) return 0;
        if(l<=s&&e<=r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
    }
}seg;

int pv;

void getTree(int v)
{
    int a; cin>>a;
    if(!a){
        g[v][0] = ++pv;
        getTree(g[v][0]);
    }
    else{
        g[v][0] = a;
    }
    int b; cin>>b;
    if(!b){
        g[v][1] = ++pv;
        getTree(g[v][1]);
    }
    else g[v][1] = b;
}

int ans = 0;
int pos;

void ett(int v)
{
    if(!v) return;
    s[v] = pos;
    if(v<=N){
        arr[pos++] = v;
    }
    ett(g[v][0]); ett(g[v][1]);
    e[v] = pos;
}

void dfs(int v, bool add)
{
    if(v<=N){
        if(add){
            seg.upd(1, N, 1, v, 1);
        }
        return;
    }
    int lsz = e[g[v][0]] - s[g[v][0]];
    int rsz = e[g[v][1]] - s[g[v][1]];
    if(lsz < rsz){
        dfs(g[v][0], false);
        dfs(g[v][1], true);
        //오른쪽만 남음
        int inv = 0;
        for(int i=s[g[v][0]];i<e[g[v][0]];i++){
            inv += seg.query(1, N, 1, arr[i]+1, N);
        }
        ans += min(inv, lsz*rsz-inv);
        if(add){
            for(int i=s[g[v][0]];i<e[g[v][0]];i++){
                seg.upd(1, N, 1, arr[i], 1);
            }
        }
        else{
            for(int i=s[g[v][1]];i<e[g[v][1]];i++){
                seg.upd(1, N, 1, arr[i], -1);
            }
        }
    }
    else{
        dfs(g[v][1], false);
        dfs(g[v][0], true);
        int inv = 0;
        for(int i=s[g[v][1]];i<e[g[v][1]];i++){
            inv += seg.query(1, N, 1, arr[i]+1, N);
        }
        ans += min(inv, lsz*rsz-inv);
        if(add){
            for(int i=s[g[v][1]];i<e[g[v][1]];i++){
                seg.upd(1, N, 1, arr[i], 1);
            }
        }
        else{
            for(int i=s[g[v][0]];i<e[g[v][0]];i++){
                seg.upd(1, N, 1, arr[i], -1);
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N;
    int tt; cin>>tt;
    seg.reset(N+1);
    pv = N+1;
    getTree(N+1);
    ett(N+1);
    dfs(N+1, 0);
    cout<<ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10