Submission #1279290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279290		PieArmy	Rope (JOI17_rope)	C++20	100 / 100	2307 ms	234488 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;
	void init(int N){
		n=N;
		tree.resize(n<<2,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]+=r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	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;
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	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.query(1,i-1),cift.query(i+1,m)),max(tek.query(1,i-1),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: 20 / 20