Submission #335231

#	Time	Username	Problem	Language	Result	Execution time	Memory
335231		Plurm	Arranging Tickets (JOI17_arranging_tickets)	C++11	0 / 100	1 ms	364 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
int seg[1 << 19];
int lazy[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
void build(int c, int l, int r){
	lb[c] = l;
	rb[c] = r;
	seg[c] = 0;
	if(l == r) return;
	int k = (l+r)/2;
	build(2*c, l, k);
	build(2*c+1, k+1, r);
}

inline void prop(int c){
	seg[c] += lazy[c];
	if(lb[c] != rb[c]){
		lazy[2*c] += lazy[c];
		lazy[2*c+1] += lazy[c];
	}
	lazy[c] = 0;
}
void update(int c, int l, int r, int x = 1){
	if(lb[c] == l && rb[c] == r) lazy[c] += x;
	prop(c);
	if(lb[c] == l && rb[c] == r) return;
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		update(2*c, l, k, x);
		update(2*c+1, k+1, r, x);
	}else if(r <= k){
		update(2*c, l, r, x);
		prop(2*c+1);
	}else{
		prop(2*c);
		update(2*c+1, l, r, x);
	}
	seg[c] = max(seg[2*c], seg[2*c+1]);
}
int query(int c, int l, int r){
	prop(c);
	if(lb[c] == l && rb[c] == r) return seg[c];
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r) return max(query(2*c, l, k), query(2*c+1, k+1, r));
	else if(r <= k) return query(2*c, l, r);
	else return query(2*c+1, l, r);
}
int main(){
	int n, m;
	scanf("%d%d",&n,&m);
	vector<tuple<int,int,int> > dat;
	for(int i = 0; i < m; i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a > b) swap(a, b);
		dat.emplace_back(a,b,c);
	}
	sort(dat.begin(), dat.end(), [](tuple<int,int,int> x, tuple<int,int,int> y){
		return get<1>(x) - get<0>(x) > get<1>(y) - get<0>(y);
	});
	int lo = 1;
	int hi = m;
	int mid;
	while(lo < hi){
		mid = (lo + hi)/2;
		build(1, 1, n);
		for(auto d : dat){
			update(1, get<0>(d), get<1>(d));
		}
		bool ok = query(1, 1, n) <= mid;
		if(!ok)
		for(auto d : dat){
			if(query(1, get<0>(d), get<1>(d)) > mid){
				update(1, 1, n, 1);
				update(1, get<0>(d), get<1>(d), -2);
			}
			if(query(1, 1, n) <= mid){
				ok = true;
				break;
			}
		}
		if(ok){
			hi = mid;
		}else{
			lo = mid+1;
		}
	}
	printf("%d\n", lo);
	return 0;
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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