Submission #1279286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279286		PieArmy	Rope (JOI17_rope)	C++20	80 / 100	2593 ms	241640 KiB

rope

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

struct Seg{
	int n;
	vector<int>tree,arr;
	void init(int N){
		n=N;
		tree.resize(n<<2,0);
		arr.resize(n,0);
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=left;
			arr[left]+=r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		if(arr[tree[node*2]]<arr[tree[node*2+1]]){
			tree[node]=tree[node*2+1];
		}
		else{
			tree[node]=tree[node*2];
		}
	}
	void update(int tar,int x){
		l=tar;r=x;
		up();
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return tree[node];
		if(left>r||right<l)return 0;
		int res1=qu(node*2,left,mid),res2=qu(node*2+1,mid+1,right);
		if(arr[res1]<arr[res2])return res2;
		else return res1;
	}
	int query(int left,int right){
		l=left;r=right;
		if(l>r)return 0;
		return qu();
	}
};

int n,m;
int arr[1000023];
Seg tek,cift;
map<int,int>mpt[1000023],mpc[1000023];
int cnt[1000023];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m;
	tek.init(m+1);
	cift.init(m+1);
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		cnt[arr[i]]++;
		tek.update(arr[i],1);
		cift.update(arr[i],1);
	}
	for(int i=1;i<=n-1;i+=2){
		mpc[arr[i]][arr[i+1]]++;
		mpc[arr[i+1]][arr[i]]++;
	}
	for(int i=2;i<=n-1;i+=2){
		mpt[arr[i]][arr[i+1]]++;
		mpt[arr[i+1]][arr[i]]++;
	}
	for(int i=1;i<=m;i++){
		for(auto[a,b]:mpc[i]){
			cift.update(a,-b);
		}
		for(auto[a,b]:mpt[i]){
			tek.update(a,-b);
		}
		int res=n-cnt[i]-max(max(cift.arr[cift.query(1,i-1)],cift.arr[cift.query(i+1,m)]),max(tek.arr[tek.query(1,i-1)],tek.arr[tek.query(i+1,m)]));
		for(auto[a,b]:mpc[i]){
			cift.update(a,b);
		}
		for(auto[a,b]:mpt[i]){
			tek.update(a,b);
		}
		cout<<res<<endl;
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 20