oj.uz

답안 #203747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203747 2020-02-22T04:37:32 Z Segtree 새 집 (APIO18_new_home) C++14
10 / 100
 2093 ms 84820 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{
		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

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.0

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

Subtask #2
0 / 7.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2065 ms 55476 KB Output is correct
2 Correct 1719 ms 51168 KB Output is correct
3 Correct 2050 ms 84692 KB Output is correct
4 Correct 2093 ms 66996 KB Output is correct
5 Correct 1676 ms 63788 KB Output is correct
6 Correct 1704 ms 61836 KB Output is correct
7 Correct 1949 ms 84820 KB Output is correct
8 Correct 2001 ms 66352 KB Output is correct
9 Correct 1906 ms 65380 KB Output is correct
10 Correct 1784 ms 63528 KB Output is correct
11 Correct 1721 ms 61648 KB Output is correct
12 Correct 1733 ms 63448 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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