oj.uz

답안 #203743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203743 2020-02-22T04:24:48 Z Segtree 새 집 (APIO18_new_home) C++14
0 / 100
 620 ms 11924 KB 
#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{
		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); return 0;
	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,bef,-xs[i][j],xs[i][j]}); bef=-xs[i][j];
				v.push_back((struct st){i,0,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,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{
			kei[e.typ^1].erase(kei[e.typ^1].find(e.bef));
			kei[e.typ^0].insert(e.aft);
		}
	}
	rep(i,q)cout<<fans[i]<<endl;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:7:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i,n) for(int i=0;i<n;i++)
                  ^
new_home.cpp:30:2: note: in expansion of macro 'rep'
  rep(i,2)kei[i].insert(-1e17); return 0;
  ^~~
new_home.cpp:30:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  rep(i,2)kei[i].insert(-1e17); return 0;
                                ^~~~~~
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:39:8:
    rep(j,xs[i].size()-1){
        ~~~~~~~~~~~~~~~~        
new_home.cpp:39:4: note: in expansion of macro 'rep'
    rep(j,xs[i].size()-1){
    ^~~
new_home.cpp:40:55: 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,bef,-xs[i][j],xs[i][j]}); bef=-xs[i][j];
                                                       ^
new_home.cpp:43:60: 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,bef,-xs[i].back(),xs[i].back()});
                                                  ~~~~~~~~~~^~
new_home.cpp:48: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:54: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:55: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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 620 ms 11924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 573 ms 11000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7288 KB Output isn't correct
2 Halted 0 ms 0 KB -