全国統一プログラミング王決定戦本戦 D - Deforestation

D - Deforestation

概要

竹がN本ある。スタート時の長さはすべて0であり、時間が1経過することに全ての竹の長さは1増える。
M回の伐採があり、i回目の伐採時は時間Tiに行われ、番号LiからRiの竹が伐採される。
伐採されても時間が1経過することに全ての竹の長さは1増える。伐採された竹の長さの合計を求めよ。

制約

1 <= N, M <= 2*10^5
1 <= Ti <= 10^9

方針

ある竹について、その竹が最後に伐採された時間がその竹から得られる長さになる。（途中の伐採は関係ない）
よって各竹が最後に伐採された時間を求めてゆく。

これは順序付き集合で管理する。サンプルケース1だと下記のようなイメージ。
L:
0 {2}
1 {5}
2 {}

R:
0 {}
1 {2}
2 {5}

初期状態
s = {}
ans = 0

竹0
s.insert(2) ⇒ s={2}
s={2}なのでsの最大値は2 ⇒ 竹0からの得点は2 ⇒ ans = 2

竹1
s.insert(5) ⇒ s={2, 5}
s={2, 5}なのでsの最大値は5 ⇒ 竹1からの得点は5 ⇒ ans = 7
s.erase(2) ⇒ s={5}

竹2
s={5}なのでsの最大値は5 ⇒ 竹2からの得点は5 ⇒ ans = 12
s.erase(5) ⇒ s={}

ans = 12 を出力

感想

遅延評価付きセグメント木（セグメント木で値の更新が区間でできるやつ）そのままらしい。

解答

Submission #4326370 - 全国統一プログラミング王決定戦本戦

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, M;
	cin >> N >> M;
 
	vector<int> L[N];
	vector<int> R[N];
	rep(i, M){
		int t, l, r;
		cin >> t >> l >> r;
		L[l-1].push_back(t);
		R[r-1].push_back(t);
	}
 
	set<int> s;
	ll ans = 0;
	for(int i = 0; i < N; i++){
		for(int x : L[i]) s.insert(x);
		if(s.size() > 0) ans += *prev(s.end());
		for(int x : R[i]) s.erase(x);
	}
 
	cout << ans << endl;
}