Submission #203747

#	Time	Username	Problem	Language	Result	Execution time	Memory
203747		Segtree	New Home (APIO18_new_home)	C++14	10 / 100	2093 ms	84820 KiB

new_home

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 300010
ll n,q,k;
ll fans[N];
multiset<ll> kei[2];
struct st{
	ll col,typ,bef,aft;
	double pnt;
	bool operator<(const st&key)const{
		if(this->pnt==key.pnt)return this->typ<key.typ;
		return this->pnt<key.pnt;
	}
};
vector<ll> xs[N];//色ごとの座標のset
int main(){
	cin>>n>>k>>q;
	rep(i,n){
		ll x,t,a,b;
		cin>>x>>t>>a>>b; t--;
		xs[t].push_back(x);
	}
	rep(i,k)sort(xs[i].begin(),xs[i].end());
	rep(i,2)kei[i].insert(-1e17);
	vector<st> v;
	rep(i,k){
		if(xs[i].size()==0){
			rep(j,2)kei[j].insert(1e17);
		}
		else{
			kei[0].insert(xs[i][0]);
			ll bef=xs[i][0];
			rep(j,xs[i].size()-1){
				v.push_back((struct st){i,1+2*j,bef,-xs[i][j],xs[i][j]}); bef=-xs[i][j];
				v.push_back((struct st){i,2+2*j,bef,xs[i][j+1],(double)(xs[i][j+1]-xs[i][j])/2.0+xs[i][j]}); bef=xs[i][j+1];
			}
			v.push_back((struct st){i,1+2*(xs[i].size()-1),bef,-xs[i].back(),xs[i].back()});
		}
	}
	rep(i,q){
		ll l,y; cin>>l>>y;
		v.push_back((struct st){-1,i,0,0,l});
	}
	sort(v.begin(),v.end());
	for(auto e:v){
		if(e.col<0){
			ll ans=0;
			chmax(ans,(ll){*kei[0].rbegin()-e.pnt});
			chmax(ans,(ll){*kei[1].rbegin()+e.pnt});
			if(ans>1e9)ans=-1;
			fans[e.typ]=ans;
		}
		else{
			ll eo=e.typ%2;
			kei[eo^1].erase(kei[eo^1].find(e.bef));
			kei[eo^0].insert(e.aft);
		}
	}
	rep(i,q)cout<<fans[i]<<endl;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:7:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
new_home.cpp:40:8:
    rep(j,xs[i].size()-1){
        ~~~~~~~~~~~~~~~~        
new_home.cpp:40:4: note: in expansion of macro 'rep'
    rep(j,xs[i].size()-1){
    ^~~
new_home.cpp:41:59: warning: narrowing conversion of 'xs[i].std::vector<long long int>::operator[](((std::vector<long long int>::size_type)j))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' to 'double' inside { } [-Wnarrowing]
     v.push_back((struct st){i,1+2*j,bef,-xs[i][j],xs[i][j]}); bef=-xs[i][j];
                                                           ^
new_home.cpp:44:31: warning: narrowing conversion of '(1 + (2 * (xs[i].std::vector<long long int>::size() - 1)))' from 'std::vector<long long int>::size_type {aka long unsigned int}' to 'll {aka long long int}' inside { } [-Wnarrowing]
    v.push_back((struct st){i,1+2*(xs[i].size()-1),bef,-xs[i].back(),xs[i].back()});
                              ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:44:79: warning: narrowing conversion of 'xs[i].std::vector<long long int>::back()' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' to 'double' inside { } [-Wnarrowing]
    v.push_back((struct st){i,1+2*(xs[i].size()-1),bef,-xs[i].back(),xs[i].back()});
                                                                     ~~~~~~~~~~^~
new_home.cpp:49:37: warning: narrowing conversion of 'l' from 'll {aka long long int}' to 'double' inside { } [-Wnarrowing]
   v.push_back((struct st){-1,i,0,0,l});
                                     ^
new_home.cpp:55:35: warning: narrowing conversion of '((double)(long long int)__builtin_memcpy(&<unnamed>, & kei[0].rbegin()()).std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::operator*()() - e.st::pnt)' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
    chmax(ans,(ll){*kei[0].rbegin()-e.pnt});
                   ~~~~~~~~~~~~~~~~^~~~
new_home.cpp:9:28: note: in definition of macro 'chmax'
 #define chmax(a,b) a=max(a,b)
                            ^
new_home.cpp:56:35: warning: narrowing conversion of '((double)(long long int)__builtin_memcpy(&<unnamed>, & kei[1].rbegin()()).std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::operator*()() + e.st::pnt)' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
    chmax(ans,(ll){*kei[1].rbegin()+e.pnt});
                   ~~~~~~~~~~~~~~~~^~~~
new_home.cpp:9:28: note: in definition of macro 'chmax'
 #define chmax(a,b) a=max(a,b)
                            ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20