Submission #447843

#	Time	Username	Problem	Language	Result	Execution time	Memory
447843		koioi.org-koosaga	Hexagonal Territory (APIO21_hexagon)	C++17	60 / 100	75 ms	24140 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 300005;
const int dx[6] = {0, 1, 1, 0, -1, -1};
const int dy[6] = {1, 1, 0, -1, -1, 0};
const int mod = 1e9 + 7;

struct mint {
    int val;
    mint() { val = 0; }
    mint(const lint& v) {
        val = (-mod <= v && v < mod) ? v : v % mod;
        if (val < 0) val += mod;
    }

    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
    friend bool operator==(const mint& a, const mint& b) { return a.val == b.val; }
    friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }

    mint operator-() const { return mint(-val); }
    mint& operator+=(const mint& m) { if ((val += m.val) >= mod) val -= mod; return *this; }
    mint& operator-=(const mint& m) { if ((val -= m.val) < 0) val += mod; return *this; }
    mint& operator*=(const mint& m) { val = (lint)val*m.val%mod; return *this; }
    friend mint ipow(mint a, lint p) {
        mint ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend mint inv(const mint& a) { assert(a.val); return ipow(a, mod - 2); }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }

    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
    operator int64_t() const {return val; }
};

lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

bool turn(vector<pi> &a){
	lint A = 0;
	for(int i = 2; i < sz(a); i++) A += ccw(a[0], a[i-1], a[i]);
	return A > 0;
}

struct node{
	int p, s, e;
	bool operator<(const node &n)const{
		return pi(p, s) < pi(n.p, n.s);
	}
};

vector<int> len[200005];
vector<node> vect;
vector<int> gph[MAXN];

mint solve(int x, int p, int d){
	mint ret = mint(d) * mint(vect[x].e - vect[x].s + 1);
	for(auto &i : gph[x]){
		if(i != p) ret += solve(i, x, d + 1);
	}
	return ret;
}


int solve(vector<pi> v){
	vect.clear();
	for(int i = 0; i < MAXN; i++){
		gph[i].clear();
	}
	int xmin = 1e9;
	if(!turn(v)) reverse(v.begin() + 1, v.end());
	for(auto &[x, y] : v){
		xmin = min(xmin, x);
	}
	int xmax = 0;
	for(auto &[x, y] : v){
		x -= xmin;
		xmax = max(xmax, x);
	}
	for(int i = 0; i < sz(v); i++){
		auto s = v[i], e = v[(i + 1) % sz(v)];
		auto p = v[(i + sz(v) - 1) % sz(v)];
		if(s.first == e.first){
			if(s.second < e.second){
				if(p.first < s.first) len[s.first].push_back(s.second);
			}
			else{
				if(p.first > s.first) len[s.first].push_back(s.second);
			}
			continue;
		}
		int delta = (e.second - s.second) / (e.first - s.first);
		if(s.first < e.first){
			if(p.first < s.first || (p.first == s.first && p.second > s.second)) len[s.first].push_back(s.second);
			if(p.first > s.first){
				len[s.first].push_back(s.second);
				len[s.first].push_back(s.second);
			}
			for(int j = s.first + 1; j < e.first; j++) len[j].push_back(s.second + delta * (j - s.first));
		}
		else if(s.first > e.first){
			if(p.first > s.first || (p.first == s.first && p.second < s.second)) len[s.first].push_back(s.second);
			if(p.first < s.first){
				len[s.first].push_back(s.second);
				len[s.first].push_back(s.second);
			}
			for(int j = s.first - 1; j > e.first; j--) len[j].push_back(s.second + delta * (j - s.first));
		}
	}
	for(int i = 0; i <= xmax; i++){
		assert(sz(len[i]) % 2 == 0);
		sort(all(len[i]));
		vector<int> nlen = {len[i][0]};
		for(int j = 1; j < sz(len[i]) / 2; j++){
			if(len[i][2*j-1] + 1 == len[i][2*j]) continue;
			nlen.push_back(len[i][2*j-1]);
			nlen.push_back(len[i][2*j]);
		}
		nlen.push_back(len[i].back());
		len[i].clear();
		for(int j = 0; j < sz(nlen) / 2; j++){
			vect.push_back({i, nlen[2*j], nlen[2*j+1]});
		}
	}
		auto insec = [&](int j, int k){
			return max(vect[j].s, vect[k].s) <= min(vect[j].e + 1, vect[k].e);
		};
	for(int i = 0; i < xmax; i++){
		int p = lower_bound(all(vect), (node){i, -int(1e9), -1}) - vect.begin();
		int q = lower_bound(all(vect), (node){i+1, -int(1e9), -1}) - vect.begin();
		int r = lower_bound(all(vect), (node){i+2, -int(1e9), -1}) - vect.begin();
		int k = q;
		for(int j = p; j < q; j++){
			while(k < r && vect[k].e < vect[j].s) k++;
			if(insec(j, k)){
				while(k < r && insec(j, k)){
					gph[j].push_back(k);
					gph[k].push_back(j);
					k++;
				}
				k--;
			}
		}
	}
//	cout << "sz(vect) = " << sz(vect) << endl;
	for(int i = 0; i < sz(vect); i++){
//		printf("vect[%d] =(%d %d %d)\n", i, vect[i].p, vect[i].s, vect[i].e);
	}
	mint ans = 0;
	for(int i = 0; i < sz(vect); i++){
		if(vect[i].p == -xmin && vect[i].s <= 0 && 0 <= vect[i].e){
//			cout << "init " << i << endl;
			return solve(i, -1, 0);
		}
	}
	assert(0);
}

int draw_territory(int N, int _A, int _B,
		std::vector<int> D, std::vector<int> L) {
	for(auto &i : D) i--;
	vector<pi> a(N);
	for(int i = 1; i < N; i++){
		a[i].first = a[i-1].first + dx[D[i-1]] * L[i-1];
		a[i].second = a[i-1].second + dy[D[i-1]] * L[i-1];
	}
	lint A = 0;
	lint B = accumulate(all(L), 0ll);
	for(int i = 2; i < N; i++) A += ccw(a[0], a[i-1], a[i]);
	A = abs(A);
	lint I = (A - B + 2) / 2;
	mint sumA = mint(I + B) * mint(_A);
	mint sumB = 0;
	for(int _ = 0; _ < 3; _++){
		if(_B == 0) continue;
		vector<pi> a(N);
		for(int i = 1; i < N; i++){
			a[i].first = a[i-1].first + dx[D[i-1]] * L[i-1];
			a[i].second = a[i-1].second + dy[D[i-1]] * L[i-1];
		}
		sumB += solve(a);
		for(auto &j : D) j = (j + 1) % 6;
	}
	return sumA + mint(_B) * sumB / mint(2);
}

Compilation message (stderr)

hexagon.cpp: In function 'int solve(std::vector<std::pair<int, int> >)':
hexagon.cpp:162:7: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  162 |  mint ans = 0;
      |       ^~~

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 19 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16