Submission #259629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259629	2020-08-08T05:35:22 Z	임성재(#5054)	None (JOI12_constellation)	C++17	0 / 100	67 ms	7552 KB

constellation

#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

#	Verdict	Memory	Grader output
1	Correct	384 KB	Output is correct
2	Incorrect	384 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #2
0.0 / 10.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-