제출 #587786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587786		LastRonin	Team Contest (JOI22_team)	C++14	73 / 100	2119 ms	919592 KiB

team

#pragma GCC optimize("O3")

#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 2e5 + 1;
const int M = 5E5 + 1;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;

int n;    
int a[N], b[N], c[N];
int sa[N], sb[N], sc[N];


struct node {
	node *l = nullptr, *r = nullptr;
	int val = 0;
} *Brt = new node(), *Crt = new node();

struct tdnode {
	tdnode *l = nullptr, *r = nullptr;
	node *val = nullptr;
	tdnode() {
		val = new node();
	}
} *tdrt = new tdnode();

vector<ll> scan[M];

void upd(int p, int z, node *v, ll tl = 0, ll tr = 1e8 + 1) {
	if(tl == tr) {
		v->val = max(v->val, z);
		return;
	}
	ll m = (tl + tr) >> 1ll;
	if(p <= m) {
		if(!v->l)v->l = new node();
		upd(p, z, v->l, tl, m);
	} else {
		if(!v->r)v->r = new node();
		upd(p, z, v->r, m + 1, tr);
	}
	v->val = max(v->val, z);
}
int get(int l, int r, node *v, ll tl = 0, ll tr = 1e8 + 1) {
	if(l > tr || tl > r || !v) 
		return 0;
	if(l <= tl && tr <= r) 
		return v->val;
	ll m = (tl + tr) >> 1ll;
	return max(get(l, r, v->l, tl, m), get(l, r, v->r, m + 1, tr));
}

void upd2(ll x, ll y, ll z, tdnode *v, ll tl = 0, ll tr = 1e8 + 1) {
	if(tl == tr) {
		upd(y, z, v->val);
		return;
	}
	ll m = (tl + tr) >> 1ll;
	if(x <= m) {
		if(!v->l)v->l = new tdnode();
		upd2(x, y, z, v->l, tl, m);
	} else {
		if(!v->r)v->r = new tdnode();
		upd2(x, y, z, v->r, m + 1, tr);
	}
	upd(y, z, v->val);
}

int get2(int lx, int rx, int ly, int ry, tdnode *v, ll tl = 0, ll  tr = 1e8 + 1) {
	if(lx > tr || rx < tl || !v)return 0;
	if(lx <= tl && tr <= rx) {
		return get(ly, ry, v->val);
	}
	ll m = (tl + tr) >> 1ll;
	return max(get2(lx, rx, ly, ry, v->l, tl , m), get2(lx, rx, ly, ry, v->r, m + 1, tr));
}


bool comp2(int i, int j) {
	return b[i] < b[j];
}

bool comp1(int i, int j) {
	return c[i] < c[j];
}

int main() {
	speed;
	cin >> n;
	vector<int> g;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
		g.pb(a[i]);
		g.pb(b[i]);
		g.pb(c[i]);
	}
	sort(g.begin(), g.end());
	g.erase(unique(g.begin(), g.end()), g.end());
	for(int j = 1; j <= n; j++) {
		sa[j] = lower_bound(g.begin(), g.end(), a[j]) - g.begin() + 1;
		scan[sa[j]].pb(j);		
	}
	ll sum = -1;
	for(int i = 1; i <= g.size(); i++) {
		for(auto u : scan[i]) {
			ll z = get2(b[u] + 1, 1e8, c[u] + 1, 1e8, tdrt);		
			if(z)sum = max(sum, a[u] + z);
		}
		vector<pill> aa;
		sort(scan[i].begin(), scan[i].end(), comp1);
		for(auto u : scan[i]) {
			upd(c[u], b[u], Crt);	
			ll gt2 = get(0, c[u] - 1, Crt);
			if(gt2 > b[u])aa.pb(mp(gt2, c[u]));								
		}
		sort(scan[i].begin(), scan[i].end(), comp2);
		for(auto u : scan[i]) {
			upd(b[u], c[u], Brt);
			ll gt = get(0, b[u] - 1, Brt);
			if(gt > c[u])aa.pb(mp(b[u], gt));
		}
		for(auto u : aa) {
			upd2(u.f, u.s, u.f + u.s, tdrt);
		}
	}
	cout << sum;
}

컴파일 시 표준 에러 (stderr) 메시지

team.cpp: In function 'int main()':
team.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 1; i <= g.size(); i++) {
      |                 ~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 27