oj.uz

Submission #1067108

# Submission time Handle Problem Language Result Execution time Memory
1067108 2024-08-20T11:30:25 Z AdamGS Radio Towers (IOI22_towers) C++17
0 / 100
 679 ms 33732 KB 
#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
ll T[LIM], jaki[LIM], n;
vector<ll>trma[4*LIM];
ll trmi[4*LIM], N=1;
set<pair<ll,ll>>S, P;
vector<pair<ll,ll>>V;
void dodaj(int x) {
	auto it=S.lower_bound({x, -1}); ++it;
	auto a=*it;
	P.insert({abs(T[x]-T[a.st]), x});
}
void usun(int x) {
	auto it=S.lower_bound({x, -1}); ++it;
	auto a=*it;
	P.erase({abs(T[x]-T[a.st]), x});
}
int ile(int v, int x) {
	if(trma[v].size()==0) return 0;
	if(trma[v].back()<=x) return 0;
	int po=0, ko=trma[v].size()-1;
	while(po<ko) {
		int sr=(po+ko)/2;
		if(trma[v][sr]<=x) po=sr+1; else ko=sr;
	}
	return trma[v].size()-po;
}
int licz(int l, int r, int x) {
	l+=N; r+=N;
	int ans=ile(l, x);
	if(l!=r) ans+=ile(r, x);
	while(l/2!=r/2) {
		if(l%2==0) ans+=ile(l+1, x);
		if(r%2==1) ans+=ile(r-1, x);
		l/=2; r/=2;
	}
	return ans;
}
void init(int _n, vector<int>_H) {
	n=_n;
	while(N<n+2) N*=2;
	rep(i, 2*N) trmi[i]=-INF;
	rep(i, n) T[i+1]=_H[i];
	T[0]=T[n+1]=INF;
	int akt=2;
	jaki[0]=jaki[n+1]=1;
	rep(i, n) if((T[i]<T[i+1] && T[i+1]>T[i+2]) || (T[i]>T[i+1] && T[i+1]<T[i+2])) {
		jaki[i+1]=akt;
		akt^=3;
	}
	rep(i, n+2) if(jaki[i]) S.insert({i, jaki[i]});
	rep(i, n+2) if(!jaki[i]) trma[N+i].pb(0);
	auto it=S.begin();
	while(true) {
		auto it2=it; ++it2;
		if(it2==S.end()) break;
		auto a=*it;
		dodaj(a.st);
		++it;
	}
	V.pb({0, S.size()/2});
	while(P.size()>2) {
		auto a=*P.begin();
		usun(a.nd);
		trma[N+a.nd].pb(V.size());
		auto it=S.lower_bound({a.nd, -1});
		++it;
		auto b=*it;
		trma[N+b.st].pb(V.size());
		usun(b.st);
		--it; --it;
		b=*it;
		usun(b.st);
		++it;
		S.erase(it);
		it=S.lower_bound({a.nd, -1});
		S.erase(it);
		it=S.lower_bound({a.nd, -1});
		--it;
		b=*it;
		dodaj(b.st);
		V.pb({a.st, S.size()/2});
	}
	rep(i, n+2) if(trma[N+i].size()==0) trma[N+i].pb(INF);
	rep(i, n+2) trmi[N+i]=T[i];
	for(int i=N-1; i; --i) {
		trmi[i]=min(trmi[2*i], trmi[2*i+1]);
		for(auto j : trma[2*i]) trma[i].pb(j);
		for(auto j : trma[2*i+1]) trma[i].pb(j);
		sort(all(trma[i]));
	}
}
int max_towers(int l, int r, int d) {
	++l; ++r;
	int po=0, ko=V.size()-1;
	while(po<ko) {
		int sr=(po+ko+1)/2;
		if(V[sr].st<d) po=sr; else ko=sr-1;
	}
	int x=licz(l, r, po);
	return x/2; // l=0, r=n-1
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 22356 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 6 ms 10072 KB Output is correct
4 Correct 8 ms 10072 KB Output is correct
5 Correct 11 ms 10328 KB Output is correct
6 Incorrect 6 ms 10328 KB 1st lines differ - on the 1st token, expected: '130', found: '129'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 6 ms 10072 KB Output is correct
4 Correct 8 ms 10072 KB Output is correct
5 Correct 11 ms 10328 KB Output is correct
6 Incorrect 6 ms 10328 KB 1st lines differ - on the 1st token, expected: '130', found: '129'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 679 ms 33732 KB 1st lines differ - on the 1st token, expected: '11903', found: '11902'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 15588 KB 1st lines differ - on the 1st token, expected: '7197', found: '7196'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 6 ms 10072 KB Output is correct
4 Correct 8 ms 10072 KB Output is correct
5 Correct 11 ms 10328 KB Output is correct
6 Incorrect 6 ms 10328 KB 1st lines differ - on the 1st token, expected: '130', found: '129'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 22356 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -