Submission #31149

#	Time	Username	Problem	Language	Result	Execution time	Memory
31149		gs14004	Arranging Tickets (JOI17_arranging_tickets)	C++14	45 / 100	879 ms	4768 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

struct intv{ int s, e, x; }a[100005];

int n, m;
int dx[200005], b[200005];

struct seg{
	int tree[3005];
	void init(){ memset(tree, 0, sizeof(tree)); }
	void add(int x, int v){
		while(x <= n){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}seg;

int solve(int x){
	int pnt = 0;
	priority_queue<int> pq;
	seg.init();
	for(int i=1; i<n; i++) b[i] = max(dx[i] - x, 0);
	for(int i=1; i<n; i++){
		seg.add(i, b[i] - b[i-1]);
	}
	for(int i=1; i<n; i++){
		while(pnt < m && a[pnt].s <= i){
			pq.push(a[pnt++].e);
		}
		while(seg.query(i) > 0 && !pq.empty()){
			auto l = pq.top();
			pq.pop();
			if(l <= i) continue;
			seg.add(i, -2);
			seg.add(l, 2);
			x++;
		}
		if(seg.query(i) > 0) return 1e9;
	}
	return x;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
		assert(a[i].x == 1);
		if(a[i].s > a[i].e) swap(a[i].s, a[i].e);
	}
	sort(a, a+m, [&](const intv &a, const intv &b){
			return a.s < b.s;
			});
	for(int i=0; i<m; i++){
		dx[a[i].s]++;
		dx[a[i].e]--;
	}
	for(int i=1; i<=n; i++) dx[i] += dx[i-1];
	int ans = 1e9;
	for(int i=-m; i<=m; i++){
		ans = min(ans, solve(i));
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:57:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
arranging_tickets.cpp:59:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
                                            ^

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