oj.uz

답안 #259629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259629 2020-08-08T05:35:22 Z 임성재(#5054) 별자리 (JOI12_constellation) C++17
0 / 100
 67 ms 7552 KB 
#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define em emplace
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const ll INF = 1e18;
const int inf = 1e9;
const ll Mod = inf + 7;

int n;
ll ans;
vector<pair<pll, int>> v;
ll x[100010];
ll y[100010];
int c[100010];
vector<int> st;
vector<int> one, two;
ll cnt;

ll ccw(pll a, pll b, pll c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

int main() {
	fast;

	cin >> n;

	for(int i=0; i<n; i++) {
		cin >> x[i] >> y[i] >> c[i];
		v.eb(mp(x[i], y[i]), c[i]);

		if(!c[i]) cnt++;
	}

	sort(all(v));
	sort(v.begin()+1, v.end(), [](pair<pll, int> a, pair<pll, int> b) {
		 return ccw(v[0].fi, a.fi, b.fi) < 0;
	});

	st.eb(0);
	st.eb(1);

	for(int i=2; i<v.size(); i++) {
		while(st.size() >= 2) {
			int s = st.back();
			st.pop_back();
			int f = st.back();

			if(ccw(v[f].fi, v[s].fi, v[i].fi) < 0) {
				st.eb(s);
				break;
			}
		}

		st.eb(i);
	}

	for(int i = 0; i < st.size(); i++) {
		if(v[st[i]].se == 1) one.eb(i);
		else if(v[st[i]].se == 2) two.eb(i);
		else cnt--;
	}

	if(one.size() + two.size() == 0) {
		ll k = st.size() - 1;
		ans = k * (k+1) + 2;
		ans %= Mod;
	}
	else if(two.size() == 0) {
		ans++;
		for(int i=1; i<one.size(); i++) {
			ll k = one[i] - one[i-1] - 1;
			ans += k * (k+1) / 2;
			ans %= Mod;
		}

		ll k = st.size() + one[0] - one.back() - 1;
		ans += k * (k+1) / 2;
		ans %= Mod;
	}
	else if(one.size() == 0) {
		ans++;
		for(int i=1; i<two.size(); i++) {
			ll k = two[i] - two[i-1] - 1;
			ans += k * (k+1) / 2;
			ans %= Mod;
		}

		ll k = st.size() + two[0] - two.back() - 1;
		ans += k * (k+1) / 2;
		ans %= Mod;
	}
	else if(one.front() < two.front()) {
		bool flag = false;
		for(auto i : one) {
			if(two.front() < i && i < two.back()) {
				flag = true;
			}
		}

		if(!flag) {
			ll l = lower_bound(all(one), two.front()) - one.begin() - 1;
			l = two.front() - one[l];

			ll r = lower_bound(all(one), two.back()) - one.begin();
			if(r == one.size()) r = st.size() + one.front() - two.back();
			else r = one[r] - two.back();

			ans += l * r;
			ans %= Mod;
		}
	}
	else {
		bool flag = false;
		for(auto i : two) {
			if(one.front() < i && i < one.back()) {
				flag = true;
			}
		}

		if(!flag) {
			ll l = lower_bound(all(two), one.front()) - two.begin() - 1;
			l = one.front() - two[l];

			ll r = lower_bound(all(two), one.back()) - two.begin();
			if(r == two.size()) r = st.size() + two.front() - one.back();
			else r = two[r] - one.back();

			ans += l * r;
			ans %= Mod;
		}
	}

	for(int i=0; i<cnt; i++) {
		ans *= 2;
		ans %= Mod;
	}

	cout << ans;
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2; i<v.size(); i++) {
               ~^~~~~~~~~
constellation.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < st.size(); i++) {
                 ~~^~~~~~~~~~~
constellation.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<one.size(); i++) {
                ~^~~~~~~~~~~
constellation.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<two.size(); i++) {
                ~^~~~~~~~~~~
constellation.cpp:118:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(r == one.size()) r = st.size() + one.front() - two.back();
       ~~^~~~~~~~~~~~~
constellation.cpp:138:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(r == two.size()) r = st.size() + two.front() - one.back();
       ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 10.0

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

Subtask #4
0.0 / 10.0

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

Subtask #5
0.0 / 10.0

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

Subtask #6
0.0 / 10.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 64 ms 6944 KB Output is correct
3 Correct 60 ms 7552 KB Output is correct
4 Correct 61 ms 7396 KB Output is correct
5 Correct 60 ms 7396 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 65 ms 6888 KB Output is correct
3 Incorrect 64 ms 6884 KB Output isn't correct
4 Halted 0 ms 0 KB -