oj.uz

답안 #706839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706839 2023-03-07T21:38:43 Z Antekb Two Antennas (JOI19_antennas) C++14
100 / 100
 593 ms 43048 KB 
#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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24940 KB Output is correct
2 Correct 13 ms 24940 KB Output is correct
3 Correct 13 ms 24940 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24940 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24868 KB Output is correct
8 Correct 13 ms 24916 KB Output is correct
9 Correct 12 ms 24960 KB Output is correct
10 Correct 13 ms 24916 KB Output is correct
11 Correct 13 ms 24880 KB Output is correct
12 Correct 14 ms 24972 KB Output is correct
13 Correct 13 ms 24908 KB Output is correct
14 Correct 14 ms 24932 KB Output is correct
15 Correct 13 ms 24912 KB Output is correct
16 Correct 13 ms 24936 KB Output is correct
17 Correct 14 ms 24916 KB Output is correct
18 Correct 13 ms 24916 KB Output is correct
19 Correct 13 ms 24916 KB Output is correct
20 Correct 13 ms 24896 KB Output is correct
21 Correct 13 ms 24944 KB Output is correct
22 Correct 13 ms 24916 KB Output is correct
23 Correct 13 ms 24960 KB Output is correct
24 Correct 13 ms 24916 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24940 KB Output is correct
2 Correct 13 ms 24940 KB Output is correct
3 Correct 13 ms 24940 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24940 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24868 KB Output is correct
8 Correct 13 ms 24916 KB Output is correct
9 Correct 12 ms 24960 KB Output is correct
10 Correct 13 ms 24916 KB Output is correct
11 Correct 13 ms 24880 KB Output is correct
12 Correct 14 ms 24972 KB Output is correct
13 Correct 13 ms 24908 KB Output is correct
14 Correct 14 ms 24932 KB Output is correct
15 Correct 13 ms 24912 KB Output is correct
16 Correct 13 ms 24936 KB Output is correct
17 Correct 14 ms 24916 KB Output is correct
18 Correct 13 ms 24916 KB Output is correct
19 Correct 13 ms 24916 KB Output is correct
20 Correct 13 ms 24896 KB Output is correct
21 Correct 13 ms 24944 KB Output is correct
22 Correct 13 ms 24916 KB Output is correct
23 Correct 13 ms 24960 KB Output is correct
24 Correct 13 ms 24916 KB Output is correct
25 Correct 122 ms 29652 KB Output is correct
26 Correct 26 ms 25496 KB Output is correct
27 Correct 171 ms 31564 KB Output is correct
28 Correct 174 ms 31728 KB Output is correct
29 Correct 125 ms 29728 KB Output is correct
30 Correct 122 ms 29360 KB Output is correct
31 Correct 156 ms 30992 KB Output is correct
32 Correct 171 ms 31624 KB Output is correct
33 Correct 161 ms 31176 KB Output is correct
34 Correct 91 ms 28176 KB Output is correct
35 Correct 171 ms 31540 KB Output is correct
36 Correct 173 ms 31716 KB Output is correct
37 Correct 102 ms 28240 KB Output is correct
38 Correct 170 ms 30724 KB Output is correct
39 Correct 38 ms 25744 KB Output is correct
40 Correct 175 ms 30900 KB Output is correct
41 Correct 128 ms 29108 KB Output is correct
42 Correct 169 ms 30644 KB Output is correct
43 Correct 67 ms 26892 KB Output is correct
44 Correct 173 ms 30660 KB Output is correct
45 Correct 41 ms 25968 KB Output is correct
46 Correct 167 ms 30652 KB Output is correct
47 Correct 55 ms 26472 KB Output is correct
48 Correct 170 ms 30724 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 30460 KB Output is correct
2 Correct 337 ms 31180 KB Output is correct
3 Correct 229 ms 29392 KB Output is correct
4 Correct 336 ms 30984 KB Output is correct
5 Correct 147 ms 27752 KB Output is correct
6 Correct 338 ms 30924 KB Output is correct
7 Correct 296 ms 30256 KB Output is correct
8 Correct 335 ms 31052 KB Output is correct
9 Correct 57 ms 26528 KB Output is correct
10 Correct 336 ms 35276 KB Output is correct
11 Correct 204 ms 31308 KB Output is correct
12 Correct 345 ms 35280 KB Output is correct
13 Correct 254 ms 32868 KB Output is correct
14 Correct 256 ms 32964 KB Output is correct
15 Correct 252 ms 33028 KB Output is correct
16 Correct 244 ms 33468 KB Output is correct
17 Correct 308 ms 32932 KB Output is correct
18 Correct 253 ms 33420 KB Output is correct
19 Correct 255 ms 32760 KB Output is correct
20 Correct 253 ms 33128 KB Output is correct
21 Correct 248 ms 32692 KB Output is correct
22 Correct 254 ms 32964 KB Output is correct
23 Correct 259 ms 32768 KB Output is correct
24 Correct 242 ms 32868 KB Output is correct

Subtask #4
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24940 KB Output is correct
2 Correct 13 ms 24940 KB Output is correct
3 Correct 13 ms 24940 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24940 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24868 KB Output is correct
8 Correct 13 ms 24916 KB Output is correct
9 Correct 12 ms 24960 KB Output is correct
10 Correct 13 ms 24916 KB Output is correct
11 Correct 13 ms 24880 KB Output is correct
12 Correct 14 ms 24972 KB Output is correct
13 Correct 13 ms 24908 KB Output is correct
14 Correct 14 ms 24932 KB Output is correct
15 Correct 13 ms 24912 KB Output is correct
16 Correct 13 ms 24936 KB Output is correct
17 Correct 14 ms 24916 KB Output is correct
18 Correct 13 ms 24916 KB Output is correct
19 Correct 13 ms 24916 KB Output is correct
20 Correct 13 ms 24896 KB Output is correct
21 Correct 13 ms 24944 KB Output is correct
22 Correct 13 ms 24916 KB Output is correct
23 Correct 13 ms 24960 KB Output is correct
24 Correct 13 ms 24916 KB Output is correct
25 Correct 122 ms 29652 KB Output is correct
26 Correct 26 ms 25496 KB Output is correct
27 Correct 171 ms 31564 KB Output is correct
28 Correct 174 ms 31728 KB Output is correct
29 Correct 125 ms 29728 KB Output is correct
30 Correct 122 ms 29360 KB Output is correct
31 Correct 156 ms 30992 KB Output is correct
32 Correct 171 ms 31624 KB Output is correct
33 Correct 161 ms 31176 KB Output is correct
34 Correct 91 ms 28176 KB Output is correct
35 Correct 171 ms 31540 KB Output is correct
36 Correct 173 ms 31716 KB Output is correct
37 Correct 102 ms 28240 KB Output is correct
38 Correct 170 ms 30724 KB Output is correct
39 Correct 38 ms 25744 KB Output is correct
40 Correct 175 ms 30900 KB Output is correct
41 Correct 128 ms 29108 KB Output is correct
42 Correct 169 ms 30644 KB Output is correct
43 Correct 67 ms 26892 KB Output is correct
44 Correct 173 ms 30660 KB Output is correct
45 Correct 41 ms 25968 KB Output is correct
46 Correct 167 ms 30652 KB Output is correct
47 Correct 55 ms 26472 KB Output is correct
48 Correct 170 ms 30724 KB Output is correct
49 Correct 302 ms 30460 KB Output is correct
50 Correct 337 ms 31180 KB Output is correct
51 Correct 229 ms 29392 KB Output is correct
52 Correct 336 ms 30984 KB Output is correct
53 Correct 147 ms 27752 KB Output is correct
54 Correct 338 ms 30924 KB Output is correct
55 Correct 296 ms 30256 KB Output is correct
56 Correct 335 ms 31052 KB Output is correct
57 Correct 57 ms 26528 KB Output is correct
58 Correct 336 ms 35276 KB Output is correct
59 Correct 204 ms 31308 KB Output is correct
60 Correct 345 ms 35280 KB Output is correct
61 Correct 254 ms 32868 KB Output is correct
62 Correct 256 ms 32964 KB Output is correct
63 Correct 252 ms 33028 KB Output is correct
64 Correct 244 ms 33468 KB Output is correct
65 Correct 308 ms 32932 KB Output is correct
66 Correct 253 ms 33420 KB Output is correct
67 Correct 255 ms 32760 KB Output is correct
68 Correct 253 ms 33128 KB Output is correct
69 Correct 248 ms 32692 KB Output is correct
70 Correct 254 ms 32964 KB Output is correct
71 Correct 259 ms 32768 KB Output is correct
72 Correct 242 ms 32868 KB Output is correct
73 Correct 494 ms 39924 KB Output is correct
74 Correct 357 ms 35856 KB Output is correct
75 Correct 448 ms 39880 KB Output is correct
76 Correct 569 ms 43016 KB Output is correct
77 Correct 301 ms 35076 KB Output is correct
78 Correct 500 ms 40548 KB Output is correct
79 Correct 534 ms 41696 KB Output is correct
80 Correct 593 ms 43048 KB Output is correct
81 Correct 244 ms 33544 KB Output is correct
82 Correct 463 ms 39000 KB Output is correct
83 Correct 423 ms 38924 KB Output is correct
84 Correct 585 ms 42956 KB Output is correct
85 Correct 410 ms 36512 KB Output is correct
86 Correct 465 ms 39508 KB Output is correct
87 Correct 283 ms 33956 KB Output is correct
88 Correct 456 ms 39948 KB Output is correct
89 Correct 509 ms 37692 KB Output is correct
90 Correct 469 ms 39956 KB Output is correct
91 Correct 317 ms 34792 KB Output is correct
92 Correct 467 ms 39652 KB Output is correct
93 Correct 293 ms 33848 KB Output is correct
94 Correct 461 ms 39512 KB Output is correct
95 Correct 305 ms 34548 KB Output is correct
96 Correct 452 ms 39536 KB Output is correct