提出 #70277094

---

ソースコード 拡げる

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint998244353 mi;
using namespace std;
#define all(a) a.begin(),a.end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
constexpr ll mod=998244353;
constexpr ll inf=3e18;

struct S{
	ll pos,lr;
};
struct F{
	ll pos,lr;
	bool operator==(const F &rhs) const{
		return pos==rhs.pos&&lr==rhs.lr;
	}
};
const F ID={inf,-1};
S op(S a,S b){if(a.pos<b.pos)return a;return b;}
S e(){return {inf,-1};}
S mapping(F f,S x){return (f==ID?x:S({f.pos,f.lr}));}
F composition(F f,F g){return (f==ID?g:f);};
F id(){return ID;}

int main(){
	int n;
	cin>>n;
	vector<ll>w(n);
	rep(i,n)cin>>w[i];
	vector<S>V(n,{0,0});
	lazy_segtree<S,op,e,F,mapping,composition,id> seg(V);

	int q;
	cin>>q;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			int v;
			cin>>v;
			auto it=seg.get(v-1);
			ll pos_l;
			if(it.lr==0)pos_l=it.pos;
			else pos_l=it.pos-w[v-1];
			seg.apply(0,v,{pos_l,0});
		}
		else if(t==2){
			int v;
			cin>>v;
			auto it=seg.get(v-1);
			ll pos_r;
			if(it.lr==0)pos_r=it.pos+w[v-1];
			else pos_r=it.pos;
			seg.apply(0,v,{pos_r,1});
		}
		else{
			ll x;
			cin>>x;
			int lb=-1,ub=n;
			while(ub-lb>1){
				int mi=(ub+lb)/2;
				auto it=seg.get(mi);
				ll li,ri;
				if(it.lr==0){
					li=it.pos;
					ri=li+w[mi];
				}
				else{
					ri=it.pos;
					li=ri-w[mi];
				}
				if(li<=x&&x<ri){
					ub=mi;
				}
				else lb=mi;
			}
			cout<<n-ub<<endl;
		}
	}
}

提出情報

ジャッジ結果