제출 #335236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335236		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;
	lazy[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);
		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<1>(y);
	});
	int ans = 1e9;
	for(int l = 1; l <= n; l++){
		for(int r = l; r <= n; r++){
			build(1, 1, n);
			for(auto d : dat){
				if(get<0>(d) <= l && get<1>(d) >= r){
					update(1, 1, n);
					update(1, get<0>(d), get<1>(d), -2);
				}else{
					update(1, get<0>(d), get<1>(d));
				}
			}
			ans = min(ans, query(1, 1, n));
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   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