제출 #549298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549298		brunnorezendes	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	1 ms	1192 KiB

arranging_tickets

#include <bits/stdc++.h>
#define maxn 200000
#define s second
#define f first

using namespace std;

typedef pair<int,int> ii;
typedef vector <ii> vii;
typedef vector <int> vi;

int seg[4*maxn], lazy[4*maxn];

void unlazy(int u){
	seg[u]+=lazy[u];
	lazy[(2*u)] += lazy[u];
	lazy[(2*u)+1] += lazy[u];
	lazy[u]=0;
}

void update(int u, int l, int r, int ql, int qr, int c){
	int mid;
	mid = (l+r)/2;
	unlazy(u);
	if(ql>r || qr<l) mid=0;
	else{
		if(l>=ql && r<=qr) lazy[u]+=c;
		else{
			update(2*u, l, mid, ql, qr, c);
			update((2*u)+1, mid+1, r, ql, qr, c);
			seg[u] = max(seg[2*u], seg[(2*u)+1]);
		}
		unlazy(u);
	}
}

int main(){
	int n, i, m, people[maxn], a, b, ant, atu;
	vii stations, v;
	cin >> n >> m;
	for(i=0;i<m;i++){
		cin >> a >> b >> people[i];
		if(a>b) swap(a,b);
		stations.push_back({a, b});
		v.push_back({b-a, i});
	}
	sort(v.begin(), v.end());
	for(i=0;i<m;i++){
		update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, people[v[i].s]);
	}
	for(i=m-1;i>=0;i--){
		unlazy(1);
		ant = seg[1];
		update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, -people[v[i].s]);
		if(stations[v[i].s].f) update(1, 0, n-1, 0, stations[v[i].s].f-1, people[v[i].s]);
		update(1, 0, n-1, stations[v[i].s].s, n-1, people[v[i].s]);
		unlazy(1);
		atu = seg[1];
		if(ant<=atu){
			update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, people[v[i].s]);
			if(stations[v[i].s].f) update(1, 0, n-1, 0, stations[v[i].s].f-1, -people[v[i].s]);
			update(1, 0, n-1, stations[v[i].s].s, n-1, -people[v[i].s]);
		}
	}
	cout << seg[1] << endl;
	return (0);
}

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