Submission #259487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259487	2020-08-07T22:29:40 Z	dorijanlendvaj	Two Antennas (JOI19_antennas)	C++14	35 / 100	299 ms	29304 KB

antennas

//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

void compress(vi&v)
{
	set<int> s;
	for (auto a: v) s.insert(a);
	vi o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

void compress(vl&v)
{
	set<ll> s;
	for (auto a: v) s.insert(a);
	vl o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=400010,M=1<<18;
int t,n,q,h[N],a[N],b[N],dp[2010][2010];
int seg1[M*2+10],seg2[M*2+10];
vector<pii> ev[N];

void upd(int i,int x)
{
	i+=M;
	if (x!=-1) seg1[i]=seg2[i]=x;
	else seg1[i]=0,seg2[i]=MOD;
	for (i/=2;i;i/=2) seg1[i]=max(seg1[i*2],seg1[i*2+1]),seg2[i]=min(seg2[i*2],seg2[i*2+1]);
}

int ge1(int l,int r,int lo=0,int hi=M,int i=1)
{
	if (lo>=l && hi<=r) return seg1[i];
	if (lo>=r || hi<=l) return 0;
	int mid=(lo+hi)/2;
	return max(ge1(l,r,lo,mid,i*2),ge1(l,r,mid,hi,i*2+1));
}

int ge2(int l,int r,int lo=0,int hi=M,int i=1)
{
	if (lo>=l && hi<=r) return seg2[i];
	if (lo>=r || hi<=l) return MOD;
	int mid=(lo+hi)/2;
	return min(ge2(l,r,lo,mid,i*2),ge2(l,r,mid,hi,i*2+1));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
	cin>>n;
	for (int i=0;i<n;++i) cin>>h[i]>>a[i]>>b[i];
	if (n<=2000)
	{
		memset(dp,-1,sizeof(dp));
		for (int i=0;i<n;++i) for (int j=i+1;j<n;++j)
		{
			if (j-i>=a[i] && j-i>=a[j] && j-i<=b[i] && j-i<=b[j]) dp[i][j]=abs(h[i]-h[j]);
		}
		for (int le=1;le<n;++le)
		{
			for (int i=0;i<n-le;++i) dp[i][i+le+1]=max(dp[i][i+le],dp[i][i+le+1]);
			for (int i=1;i<n-le;++i) dp[i-1][i+le]=max(dp[i][i+le],dp[i-1][i+le]);
		}
		cin>>q;
		while (q--)
		{
			int l,r;
			cin>>l>>r;
			--l;
			--r;
			cout<<dp[l][r]<<en;
		}
	}
	else
	{
		memset(seg2,63,sizeof(seg2));
		int re=0;
		for (int i=0;i<n;++i)
		{
			for (auto a: ev[i])
			{
				upd(a.x,a.y);
			}
			int mi=ge2(i-b[i],i-a[i]+1);
			int ma=ge1(i-b[i],i-a[i]+1);
			/*cout<<i-b[i]<<' '<<i-a[i]+1<<' '<<mi<<' '<<h[i]<<' '<<ma<<' '<<re<<' '<<h[i]-mi<<' '<<ma-h[i]<<endl;
			for (int j=0;j<n;++j) cout<<seg1[i+M]<<' ';
			cout<<en<<en;*/
			re=max(re,h[i]-mi);
			re=max(re,ma-h[i]);
			ev[i+a[i]].eb(i,h[i]);
			ev[i+b[i]+1].eb(i,-1);
		}
		cout<<re<<en;
	}
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	25600 KB	Output is correct
2	Correct	19 ms	25600 KB	Output is correct
3	Correct	15 ms	25600 KB	Output is correct
4	Correct	16 ms	25632 KB	Output is correct
5	Correct	17 ms	25600 KB	Output is correct
6	Correct	19 ms	25600 KB	Output is correct
7	Correct	17 ms	25600 KB	Output is correct
8	Correct	16 ms	25600 KB	Output is correct
9	Correct	15 ms	25600 KB	Output is correct
10	Correct	17 ms	25600 KB	Output is correct
11	Correct	15 ms	25600 KB	Output is correct
12	Correct	16 ms	25728 KB	Output is correct
13	Correct	15 ms	25600 KB	Output is correct
14	Correct	16 ms	25600 KB	Output is correct
15	Correct	15 ms	25728 KB	Output is correct
16	Correct	15 ms	25600 KB	Output is correct
17	Correct	16 ms	25592 KB	Output is correct
18	Correct	15 ms	25600 KB	Output is correct
19	Correct	15 ms	25600 KB	Output is correct
20	Correct	15 ms	25600 KB	Output is correct
21	Correct	15 ms	25600 KB	Output is correct
22	Correct	15 ms	25600 KB	Output is correct
23	Correct	15 ms	25600 KB	Output is correct
24	Correct	16 ms	25600 KB	Output is correct

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	25600 KB	Output is correct
2	Correct	19 ms	25600 KB	Output is correct
3	Correct	15 ms	25600 KB	Output is correct
4	Correct	16 ms	25632 KB	Output is correct
5	Correct	17 ms	25600 KB	Output is correct
6	Correct	19 ms	25600 KB	Output is correct
7	Correct	17 ms	25600 KB	Output is correct
8	Correct	16 ms	25600 KB	Output is correct
9	Correct	15 ms	25600 KB	Output is correct
10	Correct	17 ms	25600 KB	Output is correct
11	Correct	15 ms	25600 KB	Output is correct
12	Correct	16 ms	25728 KB	Output is correct
13	Correct	15 ms	25600 KB	Output is correct
14	Correct	16 ms	25600 KB	Output is correct
15	Correct	15 ms	25728 KB	Output is correct
16	Correct	15 ms	25600 KB	Output is correct
17	Correct	16 ms	25592 KB	Output is correct
18	Correct	15 ms	25600 KB	Output is correct
19	Correct	15 ms	25600 KB	Output is correct
20	Correct	15 ms	25600 KB	Output is correct
21	Correct	15 ms	25600 KB	Output is correct
22	Correct	15 ms	25600 KB	Output is correct
23	Correct	15 ms	25600 KB	Output is correct
24	Correct	16 ms	25600 KB	Output is correct
25	Correct	65 ms	28152 KB	Output is correct
26	Correct	44 ms	25848 KB	Output is correct
27	Correct	96 ms	29176 KB	Output is correct
28	Correct	129 ms	29304 KB	Output is correct
29	Correct	69 ms	28024 KB	Output is correct
30	Correct	89 ms	28152 KB	Output is correct
31	Correct	84 ms	28540 KB	Output is correct
32	Correct	129 ms	29244 KB	Output is correct
33	Correct	87 ms	28920 KB	Output is correct
34	Correct	74 ms	27384 KB	Output is correct
35	Correct	101 ms	29048 KB	Output is correct
36	Correct	115 ms	29176 KB	Output is correct
37	Correct	74 ms	27128 KB	Output is correct
38	Correct	107 ms	28280 KB	Output is correct
39	Correct	44 ms	25976 KB	Output is correct
40	Correct	114 ms	28280 KB	Output is correct
41	Correct	85 ms	27512 KB	Output is correct
42	Correct	119 ms	28280 KB	Output is correct
43	Correct	63 ms	26488 KB	Output is correct
44	Correct	120 ms	28280 KB	Output is correct
45	Correct	49 ms	26104 KB	Output is correct
46	Correct	118 ms	28376 KB	Output is correct
47	Correct	53 ms	26360 KB	Output is correct
48	Correct	114 ms	28256 KB	Output is correct

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	260 ms	26488 KB	Output is correct
2	Correct	299 ms	28152 KB	Output is correct
3	Correct	174 ms	23292 KB	Output is correct
4	Correct	268 ms	28280 KB	Output is correct
5	Correct	109 ms	19192 KB	Output is correct
6	Correct	260 ms	28152 KB	Output is correct
7	Correct	225 ms	25976 KB	Output is correct
8	Correct	267 ms	28152 KB	Output is correct
9	Correct	39 ms	14328 KB	Output is correct
10	Correct	269 ms	28152 KB	Output is correct
11	Correct	169 ms	22164 KB	Output is correct
12	Correct	262 ms	28152 KB	Output is correct
13	Correct	183 ms	24812 KB	Output is correct
14	Correct	176 ms	24764 KB	Output is correct
15	Correct	170 ms	25424 KB	Output is correct
16	Correct	159 ms	26180 KB	Output is correct
17	Correct	185 ms	24876 KB	Output is correct
18	Correct	173 ms	25160 KB	Output is correct
19	Correct	176 ms	24812 KB	Output is correct
20	Correct	172 ms	24680 KB	Output is correct
21	Correct	178 ms	24804 KB	Output is correct
22	Correct	175 ms	25060 KB	Output is correct
23	Correct	176 ms	24760 KB	Output is correct
24	Correct	160 ms	25580 KB	Output is correct

Subtask #4
0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	25600 KB	Output is correct
2	Correct	19 ms	25600 KB	Output is correct
3	Correct	15 ms	25600 KB	Output is correct
4	Correct	16 ms	25632 KB	Output is correct
5	Correct	17 ms	25600 KB	Output is correct
6	Correct	19 ms	25600 KB	Output is correct
7	Correct	17 ms	25600 KB	Output is correct
8	Correct	16 ms	25600 KB	Output is correct
9	Correct	15 ms	25600 KB	Output is correct
10	Correct	17 ms	25600 KB	Output is correct
11	Correct	15 ms	25600 KB	Output is correct
12	Correct	16 ms	25728 KB	Output is correct
13	Correct	15 ms	25600 KB	Output is correct
14	Correct	16 ms	25600 KB	Output is correct
15	Correct	15 ms	25728 KB	Output is correct
16	Correct	15 ms	25600 KB	Output is correct
17	Correct	16 ms	25592 KB	Output is correct
18	Correct	15 ms	25600 KB	Output is correct
19	Correct	15 ms	25600 KB	Output is correct
20	Correct	15 ms	25600 KB	Output is correct
21	Correct	15 ms	25600 KB	Output is correct
22	Correct	15 ms	25600 KB	Output is correct
23	Correct	15 ms	25600 KB	Output is correct
24	Correct	16 ms	25600 KB	Output is correct
25	Correct	65 ms	28152 KB	Output is correct
26	Correct	44 ms	25848 KB	Output is correct
27	Correct	96 ms	29176 KB	Output is correct
28	Correct	129 ms	29304 KB	Output is correct
29	Correct	69 ms	28024 KB	Output is correct
30	Correct	89 ms	28152 KB	Output is correct
31	Correct	84 ms	28540 KB	Output is correct
32	Correct	129 ms	29244 KB	Output is correct
33	Correct	87 ms	28920 KB	Output is correct
34	Correct	74 ms	27384 KB	Output is correct
35	Correct	101 ms	29048 KB	Output is correct
36	Correct	115 ms	29176 KB	Output is correct
37	Correct	74 ms	27128 KB	Output is correct
38	Correct	107 ms	28280 KB	Output is correct
39	Correct	44 ms	25976 KB	Output is correct
40	Correct	114 ms	28280 KB	Output is correct
41	Correct	85 ms	27512 KB	Output is correct
42	Correct	119 ms	28280 KB	Output is correct
43	Correct	63 ms	26488 KB	Output is correct
44	Correct	120 ms	28280 KB	Output is correct
45	Correct	49 ms	26104 KB	Output is correct
46	Correct	118 ms	28376 KB	Output is correct
47	Correct	53 ms	26360 KB	Output is correct
48	Correct	114 ms	28256 KB	Output is correct
49	Correct	260 ms	26488 KB	Output is correct
50	Correct	299 ms	28152 KB	Output is correct
51	Correct	174 ms	23292 KB	Output is correct
52	Correct	268 ms	28280 KB	Output is correct
53	Correct	109 ms	19192 KB	Output is correct
54	Correct	260 ms	28152 KB	Output is correct
55	Correct	225 ms	25976 KB	Output is correct
56	Correct	267 ms	28152 KB	Output is correct
57	Correct	39 ms	14328 KB	Output is correct
58	Correct	269 ms	28152 KB	Output is correct
59	Correct	169 ms	22164 KB	Output is correct
60	Correct	262 ms	28152 KB	Output is correct
61	Correct	183 ms	24812 KB	Output is correct
62	Correct	176 ms	24764 KB	Output is correct
63	Correct	170 ms	25424 KB	Output is correct
64	Correct	159 ms	26180 KB	Output is correct
65	Correct	185 ms	24876 KB	Output is correct
66	Correct	173 ms	25160 KB	Output is correct
67	Correct	176 ms	24812 KB	Output is correct
68	Correct	172 ms	24680 KB	Output is correct
69	Correct	178 ms	24804 KB	Output is correct
70	Correct	175 ms	25060 KB	Output is correct
71	Correct	176 ms	24760 KB	Output is correct
72	Correct	160 ms	25580 KB	Output is correct
73	Incorrect	250 ms	26640 KB	Output isn't correct
74	Halted	0 ms	0 KB	-

Submission #259487

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 11.0 / 11.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 65.0

Subtask #1
2.0 / 2.0

Subtask #2
11.0 / 11.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 65.0