Submission #485424

#	Time	Username	Problem	Language	Result	Execution time	Memory
485424		NothingXD	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	608 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << H;
  debug_out(T...);
}

#define debug(...)             cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int MAXN = 4e4 + 10;
const int SQRT = 200;

struct LinkList{
	int r[MAXN], l[MAXN], sz;
	vector<int> v;
	LinkList(){
		memset(r, -1, sizeof r);
		memset(l, -1, sizeof l);
		sz = 0;
		v.push_back(0);
	}
	void add(int x, int y){
		if (x != -1) r[x] = y;
		if (y != -1) l[y] = x;
	}
	int find(int idx){
		int x = idx/SQRT;
		int ptr = v[x];
		for (int i = x * SQRT + 1; i <= idx; i++){
			ptr = r[ptr];
		}
		return ptr;
	}
	void insert(int idx, int x){
		sz++;
		int L = find(idx-1);
		int R = r[L];
		add(L, x);
		add(x, R);
		for (int i = 0; i < v.size(); i++){
			if (i * SQRT >= idx){
				v[i] = l[v[i]];
			}
		}
		if (sz / SQRT == v.size()){
			int x = find(sz-1);
			v.push_back(r[x]);
		}
	}
	int erase(int idx){
		sz--;
		int res = find(idx);
		int L = l[res];
		int R = r[res];
		for (int i = 0; i < v.size(); i++){
			if (i * SQRT >= idx){
				v[i] = r[v[i]];
			}
		}
		if (v.back() == -1) v.pop_back();
		add(L, R);
		return res;
	}
} lst;


int N;
vector<pii> v;

int main(){

	N = get_n();
	if (is_clockwise(1, 2, 3)){
		lst.insert(1, 1);
		lst.insert(2, 2);
		lst.insert(3, 3);
	}
	else{
		lst.insert(1, 3);
		lst.insert(2, 2);
		lst.insert(3, 1);
	}
	for (int i = 4; i <= N; i++){
		v.clear();
		int sz = lst.sz;
		int l = 1, r = sz + 1;
		while (l + 1 < r){
			int mid = (l + r) >> 1;
			if (is_clockwise(lst.find(l), i, lst.find(mid))) r = mid;
			else l = mid;
		}
		if (r > sz) r -= sz;
		if (!is_clockwise(lst.find(l), i, lst.find(r))) continue;
		int idx = l + 1;
		lst.insert(idx, i);
		if (l < r) r++;
		int L = r, R = L + sz - 2;
		while(L + 1 < R){
			int mid = (L + R) >> 1;
			if (is_clockwise(i, lst.find((mid > sz? mid - sz: mid)), lst.find(r))) L = mid;
			else R = mid;
		}
		int lo = r-1, hi = R;
		while(lo + 1 < hi){
			int mid = (lo + hi) >> 1;
			if (is_clockwise(i, lst.find((mid + 1 > sz? mid + 1 - sz: mid + 1)), lst.find((mid > sz? mid - sz: mid)))) lo = mid;
			else hi = mid;
		}
		while(hi > sz) hi -= sz;
		if (r > hi){
			v.push_back({sz, r});
			v.push_back({hi-1, 1});
		}
		else{
			v.push_back({hi-1, r});
		}
		L = l - sz + 2, R = l;
		while(L + 1 < R){
			int mid = (L + R) >> 1;
			if (is_clockwise(i, lst.find((mid <= 0? mid + sz: mid)), lst.find(l))) L = mid;
			else R = mid;
		}
		lo = L, hi = l + 1;
		while (lo + 1 < hi){
			int mid = (lo + hi) >> 1;
			if (is_clockwise(i, lst.find((mid <= 0? mid + sz: mid)), lst.find((mid - 1 <= 0? mid + sz: mid-1)))) hi = mid;
			else lo = mid;
		}
		while (lo <= 0) lo += sz;
		if (lo > l){
			v.push_back({sz, lo + 1});
			v.push_back({l, 1});
		}
		else{
			v.push_back({l, lo+1});
		}
		sort(all(v), greater<pii>());
		for (auto [r, l]: v){
			for (int j = r; j >= l; j--){
				lst.erase(j);
			}
		}
	}
	give_answer(lst.sz);
	return 0;
}

Compilation message (stderr)

tri.cpp: In member function 'void LinkList::insert(int, int)':
tri.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < v.size(); i++){
      |                   ~~^~~~~~~~~~
tri.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if (sz / SQRT == v.size()){
      |       ~~~~~~~~~~^~~~~~~~~~~
tri.cpp: In member function 'int LinkList::erase(int)':
tri.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int i = 0; i < v.size(); i++){
      |                   ~~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25