Submission #563107

#	Time	Username	Problem	Language	Result	Execution time	Memory
563107		amunduzbaev	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	230 ms	13004 KiB

arranging_tickets

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int N = 2e5 + 5;

struct ST{
	int tree[N << 2], P[N << 2];
	
	void flush(){
		memset(tree, 0, sizeof tree);
		memset(P, 0, sizeof P);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x<<1] += P[x], P[x<<1] += P[x];
		tree[x<<1|1] += P[x], P[x<<1|1] += P[x];
		P[x] = 0;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += v, P[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x<<1), 
		add(l, r, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<int> l(m), r(m), c(m);
	for(int i=0;i<m;i++){
		cin>>l[i]>>r[i]>>c[i];
		if(l[i] > r[i]) swap(l[i], r[i]);
		r[i]--;
	}
	
	auto check = [&](int mx){
		vector<ar<int, 2>> tt;
		tree.flush();
		for(int i=0;i<m;i++){
			tt.push_back({l[i], i + 1});
			tt.push_back({r[i] + 1, -i - 1});
			tree.add(l[i], r[i], 1);
		}
		sort(tt.begin(), tt.end());
		bool ans = false;
		vector<int> used(m), is(m);
		for(int i=0, j=0;i<(int)tt.size();){
			while(j < (int)tt.size() && tt[j][0] == tt[i][0]){
				int in = abs(tt[j][1]) - 1;
				if(tt[j][1] > 0) used[in] = 1;
				else used[in] = 0;
				tree.add(l[in], r[in], (used[in] ? -1 : 1));
				j++;
			}
			
			vector<int> p;
			for(int k=0;k<m;k++){
				if(used[k]) p.push_back(k);
			}
			sort(p.begin(), p.end(), [&](int i, int j){
				return r[i] - l[i] > r[j] - l[j];
			});
			
			for(auto j : p){
				if(tree.get(0, l[j] - 1) < mx && tree.get(r[j] + 1, n) < mx){
					is[j] = 1;
					tree.add(0, l[j] - 1, 1);
					tree.add(r[j] + 1, n, 1);
				} else tree.add(l[j], r[j], 1);
			}
			//~ for(int i=0;i<=n;i++) cout<<tree.get(i, i)<<" ";
			//~ cout<<"\n";
			if(tree.get(0, N) <= mx) { ans = true; break; }
			//~ for(int i=1;i<=n;i++) cout<<tree.get(i, i)<<" ";
			//~ cout<<"\n";

			for(auto j : p){
				if(is[j]){
					is[j] = 0;
					tree.add(0, l[j] - 1, -1);
					tree.add(r[j] + 1, n, -1);
				} else tree.add(l[j], r[j], -1);
			}
			
			i = j;
		}
		
		return ans;
	};
	
	int lx = 1, rx = m;
	while(lx < rx){
		int m = (lx + rx) >> 1;
		if(check(m)) rx = m;
		else lx = m + 1;
	}
	
	cout<<lx<<"\n";
}

/*

7 5
1 6 1
4 7 1
4 5 1
3 6 1
2 3 1

answer is 3

*/ 

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