105822024-04-05 22:56:44999Branch Cuttingcpp17Wrong answer 58/100893ms13032 KiB
// Source: https://usaco.guide/general/io

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

int mod(int num, int m){
	if(num>=0)return num%m;
	else{
		return (num+m)%m;
	}
}

void bruteforce(int n, int q){
	vector<int> v(n);
	int mindex=0;
	for(int i = 0;i<n;i++){
			cin>>v[i];
	}
	for(int i = 0;i<=q;i++){
		if(i!=0){
			int a=0,b=0;	
			cin>>a>>b;
			v[a]=b;
		}
		for(int i = 0;i<n;i++){
			if(v[i]<v[mindex]||(v[i]==v[mindex]&&(i==n-1&&v[0]!=v[mindex]||v[i]!=v[i+1]))){
				mindex=i;
			}
		}
		int ans=0;
		int j=(mindex+1)%n;
		while(j!=mindex){
			if(j==(mindex+1)%n&&ans>0)break;
			if(v[mod(j-1,n)]<v[j]){
				ans++;
				j++;
			}
			j++;
			j%=n;
		}
		cout<<ans<<' ';
	}
}


int n;

bool check(int x, int l, int r) {
    // Check if x lies within the CIRCULAR interval [l, r]
    if (r >= l)
        return x >= l && x <= r;
    else
        return x >= l || x <= r;
}

int getS(int l, int r) {
    // Normalize l and r to be within the range of the array
    l = (l + n) % n;
    r = (r + n) % n;

    // Calculate the size of the circular interval [l, r]
    if (r >= l)
        return r - l + 1;
    else
        return n - l + r + 1;
}

int cir(int x){
	if(x>=0)return x%n;
	else return x+n;
}

map<int,int> s;
int ans;

void ansu(int l,int r){
	ans+=getS(l,r)/2;
	s[l]=r;
}

void alga(int X){
	auto it=s.upper_bound(X);
	if(it==s.begin()){
		it=s.end();
	}
	it--;
	int l=(*it).first,r=(*it).second;
	if(check(X,l,r)){
		s.erase(l);
		ans-=getS(l,r)/2;
		if(getS(l,r)!=2){
			if(l==X){
				ansu(cir(l+1),r);
			}
			else if(r==X){
				ansu(l,cir(r-1));
			}
			else{
				ansu(l,cir(X-1));
				ansu(cir(X+1),r);
			}
		}
	}
}

void belga(int X, int mode){
	if(s.empty()){
		if(mode==1)ansu(X,cir(X+1));
		if(mode==2)ansu(cir(X-1),X);
		if(mode==3)ansu(cir(X-1),cir(X+1));
		return;
	}
	auto it=s.upper_bound(X);
	if(mode==1){
		if(it==s.end())it=s.begin();
		int l=(*it).first,r=(*it).second;
		if(cir(X+1)==l){
			ans-=getS(l,r)/2;
			s.erase(it);
			ansu(X,r);
		}
		else{
			ansu(X,cir(X+1));
		}
	}
	if(mode==2){
		if(it==s.begin())it=s.end();
		it--;
		int l=(*it).first,r=(*it).second;
		if(cir(X-1)==r){
			ans-=getS(l,r)/2;
			s.erase(it);
			ansu(l,X);
		}
		else{
			ansu(cir(X-1),X);
		}
	}
	if(mode==3){
		if(it==s.end())it=s.begin();
		auto itt=it;
		if(it==s.begin())it=s.end();
		it--;
		int l2=(*itt).first,r2=(*itt).second;
		int l=(*it).first,r=(*it).second;
		if(cir(X-1)==r&&cir(X+1)==l2){
			ans-=getS(l,r)/2;
			ans-=getS(l2,r2)/2;
			s.erase(it);
			s.erase(itt);
			ansu(l,r2);
		}
		else if(cir(X-1)==r){
			ans-=getS(l,r)/2;
			s.erase(it);
			ansu(l,cir(X+1));
		}
		else if(cir(X+1)==l2){
			ans-=getS(l2,r2)/2;
			s.erase(itt);
			ansu(cir(X-1),r2);
		}
		else ansu(cir(X-1),cir(X+1));
	}
}

int main() {
	int q;cin>>n>>q;
	if(n<=8000&&q<=8000)bruteforce(n,q);
	else{
		vector<int> v(n);
		for(int i = 0;i<n;i++){
			cin>>v[i];
		}
		for(int i = 0;i<n;i++){
			if(v[i]<v[cir(i+1)]){
				belga(cir(i+1),2);
			}
		}
		cout<<ans<<endl;
		for(int i = 0;i<q;i++){
			int a,b;cin>>a>>b;
			alga(a);
			v[a]=b;
			if(v[a]<v[cir(a+1)]&&v[a]>v[cir(a-1)])belga(a,3);
			else if(v[a]<v[cir(a+1)]) belga(a,1);
			else if(v[a]>v[cir(a-1)]) belga(a,2);
		cout<<ans<<endl;
		}
	}
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Accepted3ms2060 KiB
subtask28/8
3Accepted3ms2272 KiB
4Accepted3ms2504 KiB
5Accepted3ms2692 KiB
6Accepted3ms2904 KiB
7Accepted3ms3148 KiB
8Accepted3ms3260 KiB
9Accepted3ms3512 KiB
10Accepted3ms3688 KiB
11Accepted3ms3808 KiB
subtask315/15
12Accepted509ms8896 KiB
13Accepted642ms8244 KiB
14Accepted657ms7580 KiB
15Accepted527ms9304 KiB
16Accepted497ms9680 KiB
17Accepted393ms5412 KiB
18Accepted393ms5368 KiB
subtask410/10
19Accepted3ms4216 KiB
20Accepted3ms4208 KiB
21Accepted17ms4328 KiB
22Accepted17ms4456 KiB
23Accepted17ms4572 KiB
24Accepted16ms4572 KiB
25Accepted14ms4568 KiB
26Accepted17ms4532 KiB
subtask525/25
27Accepted6ms4580 KiB
28Accepted4ms4560 KiB
29Accepted792ms4452 KiB
30Accepted893ms4580 KiB
31Accepted855ms4604 KiB
32Accepted615ms4452 KiB
33Accepted617ms4452 KiB
34Accepted867ms4796 KiB
subtask60/42
35Wrong answer108ms6248 KiB
36Accepted37ms6104 KiB
37Wrong answer824ms11000 KiB
38Wrong answer792ms8704 KiB
39Wrong answer796ms10788 KiB
40Wrong answer639ms6376 KiB
41Wrong answer787ms5980 KiB
42Wrong answer711ms6232 KiB
43Wrong answer782ms13032 KiB