Submission #698151

#	Time	Username	Problem	Language	Result	Execution time	Memory
698151		Sandarach151	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	324 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<4*sze+5; i++){
			leftmost[i]=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;
            }
        }
    }
    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;
            }
        }
    }
    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{
                int temp = query(queryleft, nodemid, 2*segpos+1, nodeleft, nodemid);
                if(temp!=sze){
					return temp;
				}
				else{
					return query(nodemid+1, queryright, 2*segpos+2, nodemid+1, noderight);
				}
            }
        }
    }
};

int mmin(int a, int b, int c, int d){
	return min(a, min(b, min(c, d)));
}
 
 
 
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;
            }
        }
    }
    for(int i=0; i<n; i++){
		if(arr[0][i]==0){
			int pos1 = i;
			int pos2 = i;
			int pos3 = i;
			int pos4 = i;
			while(pos1>=0 && arr[0][pos1]<=1){
				pos1--;
			}
			while(pos2<n && arr[0][pos2]<=1){
				pos2++;
			}
			while(pos3>=0 && arr[1][pos3]<=1){
				pos3--;
			}
			while(pos4<n && arr[1][pos4]<=1){
				pos4++;
			}
			if(pos1==-1){
				pos1=-1000000;
			}
			if(pos2==n){
				pos2=1000000;
			}
			if(pos3==-1){
				pos3=-1000000;
			}
			if(pos4==n){
				pos4=1000000;
			}
			int minn = mmin(i-pos1, pos2-i, i-pos3+1, pos4-i+1);
			if(i-pos1==minn){
				arr[0][pos1]--;
				arr[0][i]++;
				fincount+=i-pos1;
			}
			else if(pos2-i==minn){
				arr[0][pos2]--;
				arr[0][i]++;
				fincount+=pos2-i;
			}
			else if(i-pos3+1==minn){
				arr[1][pos3]--;
				arr[0][i]++;
				fincount+=i-pos3+1;
			}
			else{
				arr[1][pos4]--;
				arr[0][i]++;
				fincount+=pos4-i+1;
			}
		}
		if(arr[1][i]==0){
			int pos1 = i;
			int pos2 = i;
			int pos3 = i;
			int pos4 = i;
			while(pos1>=0 && arr[0][pos1]<=1){
				pos1--;
			}
			while(pos2<n && arr[0][pos2]<=1){
				pos2++;
			}
			while(pos3>=0 && arr[1][pos3]<=1){
				pos3--;
			}
			while(pos4<n && arr[1][pos4]<=1){
				pos4++;
			}
			if(pos1==-1){
				pos1=-1000000;
			}
			if(pos2==n){
				pos2=1000000;
			}
			if(pos3==-1){
				pos3=-1000000;
			}
			if(pos4==n){
				pos4=1000000;
			}
			int minn = mmin(i-pos1+1, pos2-i+1, i-pos3, pos4-i);
			if(i-pos1+1==minn){
				arr[0][pos1]--;
				arr[1][i]++;
				fincount+=i-pos1+1;
			}
			else if(pos2-i+1==minn){
				arr[0][pos2]--;
				arr[1][i]++;
				fincount+=pos2-i+1;
			}
			else if(i-pos3==minn){
				arr[1][pos3]--;
				arr[1][i]++;
				fincount+=i-pos3;
			}
			else{
				arr[1][pos4]--;
				arr[1][i]++;
				fincount+=pos4-i;
			}
		}
    }
    cout << fincount << '\n';
    return 0;
}

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