oj.uz

Submission #802962

# Submission time Handle Problem Language Result Execution time Memory
802962 2023-08-02T16:36:18 Z kshitij_sodani Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 13868 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "towers.h"

#include <vector>
int st=0;
int n;
vector<int> it;
int tree[4*200001][2];
void build(int no,int l,int r){
	if(l==r){
		tree[no][0]=it[l];
		tree[no][1]=it[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return 1e9+1;
	}
	if(aa<=l and r<=bb){
		return tree[no][0];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int query2(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no][1];
	}
	int mid=(l+r)/2;
	return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
void init(int nn, vector<int> ita) {
	n=nn;
	it=ita;
	st=0;
	build(0,0,n-1);
}
int re[100001][2];
int par[200001][20];
set<pair<int,int>> xx[2];
vector<pair<pair<int,int>,int>> yy;
map<int,int> kk;
int max_towers(int l, int r, int d) {
	if(kk.find(d)==kk.end()){
		llo ind=n;
		kk[d]++;

		yy.clear();
		xx[0].clear();
		xx[1].clear();

		for(int i=n-1;i>=0;i--){
			llo cur=query(0,0,n-1,i+1,ind-1);
			if(cur<=it[i]-d){
				llo zz=ind-1;
				while(zz>i){
					zz--;
					if(query(0,0,n-1,i+1,zz)<=it[i]-d){
						continue;
					}
					else{
						zz++;
						break;
					}
				}
				xx[0].insert({i,yy.size()});
				yy.pb({{i,zz},0});
				re[i][0]=zz;
				ind=zz-1;
			}
			else{
				re[i][0]=-1;
			}
		}
		ind=n;
		for(int i=n-1;i>=0;i--){
			llo cur=query2(0,0,n-1,i+1,ind-1);
			if(cur>=it[i]+d){
				llo zz=ind-1;
				while(zz>i){
					zz--;
					if(query2(0,0,n-1,i+1,zz)>=it[i]+d){
						continue;
					}
					else{
						zz++;
						break;
					}
				}
				re[i][1]=zz;
				xx[1].insert({i,yy.size()});
				yy.pb({{i,zz},1});
				ind=zz-1;
			}
			else{
				re[i][1]=-1;
			}
		}
		for(int i=0;i<yy.size();i++){
			par[i][0]=-1;
			auto j=xx[1-yy[i].b].lower_bound({yy[i].a.b,-1});
			if(j!=xx[1-yy[i].b].end()){
				par[i][0]=(*j).b;
			//	cout<<i<<":"<<(*j).b<<endl;
			}
		}
		for(int j=1;j<20;j++){
			for(int i=0;i<yy.size();i++){
				if(par[i][j-1]==-1){
					par[i][j]=-1;
				}
				else{
					par[i][j]=par[par[i][j-1]][j-1];
				}
			}
		}
	/*	for(auto j:yy){
			cout<<j.a.a<<","<<j.a.b<<","<<j.b<<endl;
		}
*/
		st=1;
	}
//	cout<<l<<",,,,"<<-1<<endl;
/*	for(auto j:xx[1]){
		cout<<j.a<<"//"<<j.b<<endl;
	}*/
	auto j=xx[1].lower_bound({l,-1});
	if(j==xx[1].end()){
		return 1;
	}
	int cot=(*j).b;
	//cout<<cot<<":::::"<<yy[cot].a.b<<endl;
//	cout<<((*j).a)<<"<<"<<endl;
	if(yy[cot].a.b>r){
		return 1;
	}
	//cout<<22<<endl;
	int su=1;
//cout<<cot<<";;"<<endl;
	//cout<<par[cot][0]<<":"<<par[cot][1]<<":"<<par[cot][2]<<endl;
	//cout<<par[cot][0]<<";;"<<yy[par[cot][0]].a.b<<";;"<<endl;
	for(int j=19;j>=0;j--){
		if(par[cot][j]>=0){
		//	cout<<yy[par[cot][j]].a.b<<";"<<j<<endl;
			if(yy[par[cot][j]].a.b<=r){
				cot=par[cot][j];
				su+=(1<<j);
			}
		}
	}
	//cout<<su<<",,,,"<<endl;
    return ((su)/2)+1;
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i=0;i<yy.size();i++){
      |               ~^~~~~~~~~~
towers.cpp:123:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    for(int i=0;i<yy.size();i++){
      |                ~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4030 ms 4944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 611 ms 13868 KB 14th lines differ - on the 1st token, expected: '16602', found: '16601'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4017 ms 3588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4030 ms 4944 KB Time limit exceeded
2 Halted 0 ms 0 KB -