Submission #706865

#	Time	Username	Problem	Language	Result	Execution time	Memory
706865		Antekb	Two Antennas (JOI19_antennas)	C++14	100 / 100	415 ms	41852 KiB

antennas

    #include<bits/stdc++.h>
     
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("trapv")
     
    #define st first
    #define nd second
    #define pb push_back
    #define eb emplace_back
    #define pp(x) pop_back(x)
    #define mp(a, b) make_pair(a, b)
    #define all(x) (x).begin(), (x).end()
    #define rev(x) reverse(all(x))
    #define sor(x) sort(all(x))
    #define sz(x) (int)(x).size()
    #define rsz(x) resize(x)
     
    using namespace std;
     
    ///~~~~~~~~~~~~~~~~~~~~~~~~~~
     
    template <typename H, typename T> 
    ostream& operator<<(ostream& os, pair<H, T> m){
    	return os <<"("<< m.st<<", "<<m.nd<<")";
    }
    template <typename H> 
    ostream& operator<<(ostream& os, vector<H> V){
    	os<<"{";
    	for(int i=0; i<V.size(); i++){
    		if(i)os<<" ";
    		os<<V[i];
    	}
    	os<<"}";
    	return os;
    }
     
    void debug(){cerr<<"\n";}
    template <typename H, typename... T>
    void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
    #define deb(x...) cerr<<#x<<" = ";debug(x);
    //#define deb(x...) ;
     
    ///~~~~~~~~~~~~~~~~~~~~~~~~~
     
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef vector<int> vi;
    typedef vector<pii > vii;
    typedef vector<ll> vl;
    typedef vector<pll> vll;
    typedef string str;
     
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    template <typename T>
    using ordered_set =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
     
    #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
     
    mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
     
    const int K=18, N=1<<K, INF=1e9+5, mod2=1e9+7, mod=998244353;
     
    struct modint{
    	int n=0;
    	modint(){}
    	modint(ll x){
    		n=x%mod;
    		if(n<0)n+=mod;
    	}
    	operator int(){
    		return n;
    	}
    	modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;}
    	modint operator+=(modint a){return (*this)=(*this)+a;}
    	modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;}
    	modint operator-=(modint a){return (*this)=(*this)-a;}
    	modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;}
    	modint operator*=(modint a){return (*this)=(*this)*a;}
    	modint operator^(const ll &m)const{
    		modint a(1);
    		if(m==0)return a;
    		if(m==1)return (*this);
    		a=(*this)^(m/2);
    		a*=a;
    		return a*((*this)^(m&1));
    	}
    	modint odw(){
    		return (*this)^((ll)mod-2);
    	}
    	modint operator/(modint a){return (*this)*a.odw();}
    	modint operator/=(modint a){return (*this)=(*this)/a;}
    	bool operator==(modint a){return a.n==n;}
    	friend ostream& operator<<(ostream& os, modint m) {
    		return os << m.n; 
    	}
    };
    modint fact[N], fact2[N];
    typedef vector<modint> vm;
    void factinit(){
        fact[0]=1;
        for(int i=1; i<N; i++){
            fact[i]=(fact[i-1]*modint(i))%mod;
        }
        fact2[N-1]=fact[N-1].odw();
        for(int i=N-2; i>=0; i--){
        	fact2[i]=(fact2[i+1]*modint(i+1))%mod;
        }
    }
    modint npok(int _n, int _k){
        return fact[_n]*fact2[_k]*fact2[_n-_k];
    }
    int ama[N+N], ami[N+N], ans[N+N], res[N], A[N], B[N], H[N], la[N+N], li[N+N];
    vi todo[N], toundo[N];
    void init(){
    	for(int i=0; i<N+N; i++){
    		ama[i]=la[i]=-INF;
    		ami[i]=li[i]=INF;
    		ans[i]=-1;
    	}
    }
    void prop(int v){
    	if(v<N && la[v]!=-INF){
    	int l=v+v, r=l+1;
    	//deb(v, l, ans[l], r, ans[r])
    	la[l]=max(la[l], la[v]);
    	li[l]=min(li[l], li[v]);
    	ans[l]=max(ans[l], ama[l]-li[v]);
    	ans[l]=max(ans[l], la[v]-ami[l]);
     
    	la[r]=max(la[r], la[v]);
    	li[r]=min(li[r], li[v]);
    	ans[r]=max(ans[r], ama[r]-li[v]);
    	ans[r]=max(ans[r], la[v]-ami[r]);
    	//deb(v, l, ans[l], r, ans[r], ama[r], ami[r])
    	}
    	li[v]=INF;
    	la[v]=-INF;
    }
    void propup(int v){
    	if(v/2)propup(v/2);
    	prop(v);
    }
    void act(int i, int czy){
    	//deb(i, czy);
    	i+=N;
    	propup(i);
    	if(czy==-1)ama[i]=-INF, ami[i]=INF;
    	else ama[i]=ami[i]=H[i-N];
    	for(i>>=1; i; i>>=1){
    		ama[i]=max(ama[i+i], ama[i+i+1]);
    		ami[i]=min(ami[i+i], ami[i+i+1]);
    	}
    }
    void upd(int v, int L, int R, int l, int r, int c){
    	if(L==l && r==R){
    		//deb(v, ama[v], ami[v], c);
    		la[v]=max(la[v], c);
    		li[v]=min(li[v], c);
    		ans[v]=max(ans[v], ama[v]-c);
    		ans[v]=max(ans[v], c-ami[v]);
    		//deb(v, ans[v]);
    		return;
    	}
    	int M=(L+R)>>1;
    	prop(v);
    	if(l<=M)upd(v+v, L, M, l, min(r, M), c);
    	if(r>M)upd(v+v+1, M+1, R, max(M+1, l), r, c);
    	ans[v]=max(ans[v], ans[v+v]);
    	ans[v]=max(ans[v], ans[v+v+1]);
    }
    int quer(int v, int L, int R, int l, int r){
    	if(L==l && R==r){
    		//deb(v, la[v], li[v], ama[v], ami[v], ans[v]);
    		//deb(ans[v+v], ans[v+v+1])
    		return ans[v];
    	}
    	int M=(L+R)>>1;
    	prop(v);
    	int x=-1;
    	if(l<=M)x=max(x ,quer(v+v, L, M, l, min(r, M)));
    	if(r>M)x=max(x, quer(v+v+1, M+1, R, max(M+1, l), r));
    	return x;
    }
    int main(){
    	init();
    	//factinit();
    	BOOST;
    	int n;
    	cin>>n;
    	for(int i=0; i<n; i++){
    		cin>>H[i]>>A[i]>>B[i];
    		if(i+A[i]<n)todo[i+A[i]].pb(i);
    		if(i+B[i]<n)toundo[i+B[i]].pb(i);
    	}
    	int q;
    	cin>>q;
    	vector<pair<pii, int> > Q(q);
    	for(int i=0; i<q; i++){
    		Q[i].nd=i;
    		cin>>Q[i].st.nd>>Q[i].st.st;
    		Q[i].st.nd--;
    		Q[i].st.st--;
    	}
    	sor(Q);
    	int wsk=0;
    	for(int i=0; i<n; i++){
    		for(int j:todo[i])act(j, 1);
    		//deb(max(i-B[i], 0), i-A[i], H[i])
    		if(A[i]<=i)upd(1, 0, N-1, max(i-B[i], 0), i-A[i], H[i]);
    		while(wsk<q && Q[wsk].st.st==i){
    			//deb(Q[wsk]);
    			res[Q[wsk].nd]=quer(1 ,0, N-1, Q[wsk].st.nd, Q[wsk].st.st);
    			wsk++;
    		}
    		for(int j:toundo[i])act(j, -1);
    	}
    	for(int i=0; i<q; i++){
    		cout<<res[i]<<"\n";
    	}
    }

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65