Submission #698084

#	Time	Username	Problem	Language	Result	Execution time	Memory
698084		Sandarach151	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1090 ms	212 KiB

joi2019_ho_t4

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

struct segmenttree{
    vector<int> leftmost;
    vector<int> array;
    int sze;
    segmenttree(int _sze, int arr[]):sze(_sze){
        leftmost.resize(4*sze+5);
        array.resize(sze);
        for(int i=0; i<sze; i++){
            array[i]=arr[i];
        }
        build(0, 0, sze-1);
    }
    void build(int segpos, int nodeleft, int noderight){
        if(nodeleft!=noderight){
            int nodemid = (nodeleft+noderight)/2;
            build(2*segpos+1, nodeleft, nodemid);
            build(2*segpos+2, nodemid+1, noderight);
            leftmost[segpos]=min(leftmost[2*segpos+1], leftmost[2*segpos+2]);
        }
        else{
            if(array[nodeleft]!=0){
                leftmost[segpos]=nodeleft;
            }
            else{
                leftmost[segpos]=sze+1;
            }
        }
    }
    void update(int arrpos, int val, int segpos, int nodeleft, int noderight){
        if(nodeleft!=noderight){
            int nodemid = (nodeleft+noderight)/2;
            if(arrpos<=nodemid){
                update(arrpos, val, 2*segpos+1, nodeleft, nodemid);
            }
            else{
                update(arrpos, val, 2*segpos+2, nodemid+1, noderight);
            }
            leftmost[segpos]=min(leftmost[2*segpos+1], leftmost[2*segpos+2]);
        }
        else{
            array[nodeleft]+=val;
            if(array[nodeleft]!=0){
                leftmost[segpos]=nodeleft;
            }
            else{
                leftmost[segpos]=sze+1;
            }
        }
    }
    int query(int queryleft, int queryright, int segpos, int nodeleft, int noderight){
        if(queryleft==nodeleft && queryright==noderight){
            return leftmost[segpos];
        }
        else{
            int nodemid = (nodeleft+noderight)/2;
            if(queryright<=nodemid){
                return query(queryleft, queryright, 2*segpos+1, nodeleft, nodemid);
            }
            else if(queryleft>nodemid){
                return query(queryleft, queryright, 2*segpos+2, nodemid+1, noderight);
            }
            else{
                return min(query(queryleft, nodemid, 2*segpos+1, nodeleft, nodemid), query(nodemid+1, queryright, 2*segpos+2, nodemid+1, noderight));
            }
        }
    }
};



int main(){
  	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
    int n;
    cin >> n;
    int arr[2][n];
    long long fincount = 0;
    for(int i=0; i<n; i++){
        arr[0][i]=0;
        arr[1][i]=0;
    }
    for(int i=0; i<2*n; i++){
        long long a, b;
        cin >> a >> b;
        if(a<=1){
            if(b>=2){
                arr[1][0]++;
                fincount+=b-1-a;
            }
            else{
                arr[0][0]++;
                fincount+=2-b-a;
            }
        }
        else if(a>=n){
            if(b>=2){
                arr[1][n-1]++;
                fincount+=b-2+a-n;
            }
            else{
                arr[0][n-1]++;
                fincount+=a-n+1-b;
            }
        }
        else{
            if(b>=2){
                arr[1][a-1]++;
                fincount+=b-2;
            }
            else{
                arr[0][a-1]++;
                fincount+=1-b;
            }
        }
    }
    segmenttree first(n, arr[0]);
    segmenttree second(n, arr[1]);
    for(int i=0; i<n; i++){
        if(arr[0][i]!=1){
            if(arr[0][i]>1){
                if(arr[1][i]==0){
                    int temp = arr[0][i];
                    arr[1][i]++;
                    second.update(i, 1, 0, 0, n-1);
                    arr[0][i+1]+=temp-2;
                    first.update(i+1, temp-2, 0, 0, n-1);
                    arr[0][i]-=temp-1;
                    first.update(i, 1-temp, 0, 0, n-1);
                    fincount+=temp-1;
                }
                else{
                    int temp = arr[0][i];
                    arr[0][i+1]+=temp-1;
                    first.update(i+1, temp-1, 0, 0, n-1);
                    arr[0][i]-=temp-1;
                    first.update(i, 1-temp, 0, 0, n-1);
                    fincount+=temp-1;
                }
            }
            else{
                int pos1 = first.query(i+1, n-1, 0, 0, n-1);
                int pos2 = second.query(i, n-1, 0, 0, n-1);
                if(pos1<=pos2+1){
                    arr[0][i]+=1;
                    first.update(i, 1, 0, 0, n-1);
                    arr[0][pos1]-=1;
                    first.update(pos1, -1, 0, 0, n-1);
                    fincount+=pos1-i;
                }
                else{
                    arr[0][i]+=1;
                    first.update(i, 1, 0, 0, n-1);
                    arr[1][pos2]-=1;
                    second.update(pos2, -1, 0, 0, n-1);
                    fincount+=pos2-i+1;
                }
            }
        }
        if(arr[1][i]!=1){
            if(arr[1][i]>1){
                int temp = arr[0][i];
                arr[0][i+1]+=temp-1;
                first.update(i+1, temp-1, 0, 0, n-1);
                arr[0][i]-=temp-1;
                first.update(i, 1-temp, 0, 0, n-1);
                fincount+=temp-1;
            }
            else{
                int pos1 = first.query(i, n-1, 0, 0, n-1);
                int pos2 = second.query(i+1, n-1, 0, 0, n-1);
                if(pos1+1<pos2){
                    arr[1][i]+=1;
                    second.update(i, 1, 0, 0, n-1);
                    arr[0][pos1]-=1;
                    first.update(pos1, -1, 0, 0, n-1);
                    fincount+=pos1-i+1;
                }
                else{
                    arr[1][i]+=1;
                    second.update(i, 1, 0, 0, n-1);
                    arr[1][pos2]-=1;
                    second.update(pos2, -1, 0, 0, n-1);
                    fincount+=pos2-i;
                }
            }
        }
    }
    cout << fincount << '\n';
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63