105792024-04-05 22:41:31999Branch Cuttingcpp17Hibás válasz 15/100981ms14744 KiB
// Source: https://usaco.guide/general/io

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

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;
	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)]){
			if((v[i]>v[cir(i-1)])&&s.size()){
				i++;
				belga(i,2);
			}
			else belga(i,1);
		}
	}
	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;
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1960 KiB
2Elfogadva3ms2208 KiB
subtask20/8
3Elfogadva3ms2324 KiB
4Elfogadva2ms2316 KiB
5Hibás válasz3ms2316 KiB
6Hibás válasz3ms2512 KiB
7Hibás válasz3ms2748 KiB
8Hibás válasz3ms2800 KiB
9Hibás válasz3ms2804 KiB
10Hibás válasz3ms2932 KiB
11Hibás válasz3ms2920 KiB
subtask315/15
12Elfogadva648ms8036 KiB
13Elfogadva630ms7388 KiB
14Elfogadva476ms6992 KiB
15Elfogadva493ms8512 KiB
16Elfogadva523ms9028 KiB
17Elfogadva545ms4528 KiB
18Elfogadva395ms4688 KiB
subtask40/10
19Hibás válasz3ms3292 KiB
20Elfogadva3ms3360 KiB
21Hibás válasz6ms3504 KiB
22Hibás válasz6ms3508 KiB
23Hibás válasz6ms3492 KiB
24Hibás válasz6ms3604 KiB
25Hibás válasz6ms3732 KiB
26Hibás válasz4ms3720 KiB
subtask50/25
27Hibás válasz7ms4376 KiB
28Elfogadva4ms3936 KiB
29Hibás válasz28ms4356 KiB
30Hibás válasz28ms4388 KiB
31Hibás válasz28ms4348 KiB
32Hibás válasz30ms4400 KiB
33Hibás válasz28ms4316 KiB
34Hibás válasz27ms4496 KiB
subtask60/42
35Hibás válasz134ms14740 KiB
36Elfogadva37ms5524 KiB
37Hibás válasz777ms12012 KiB
38Hibás válasz981ms13184 KiB
39Hibás válasz771ms11620 KiB
40Hibás válasz754ms14616 KiB
41Hibás válasz829ms14744 KiB
42Hibás válasz757ms14616 KiB
43Hibás válasz778ms14612 KiB