PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh
DIFFICULTY:
3074
PREREQUISITES:
PROBLEM:
You are given N segments where each segment is of the form [L_i,R_i] (1 \leq L_i \leq R_i \leq N).
It is ensured that for any two segments X and Y, one of the following conditions hold true:
- X \cap Y = X ,
- X \cap Y = Y , or
- X \cap Y = \emptyset (empty set)
Note that \cap denotes the intersection of segments.
In other words, for any two segments, either one is completely inside the other or they are completely disjoint.
The i^{th} segment (1\le i \le N) is assigned a value V_i.
A subset S = \{S_1, S_2, \ldots , S_k\} having k segments is considered good if there exists an integer array B of size k such that:
- All elements of the array B are distinct.
- B_i lies in the segment S_i.
Let the score of a good subset be defined as the sum of values of all segments of the subset. Find the maximum score of a good subset.
EXPLANATION:
First sort the segments given in the input in increasing order of their length (number of elements in them). Now iterate over the segments in the ascending order of their length. Now, Suppose we are at some segment [L, R].
There are two cases:
- There is a point in [L, R] which has not been assigned to any interval yet. Then, we can freely assign it to this interval.
- Every point has been assigned to some segment. Then, find the lowest value point in the interval and check if it is more profitable to assign it to [L, R].
Both the cases listed above can be combined into one by assuming that every point is initially assigned a value of 0. The calculation of the minimum and its position in a range along with point updates can be done efficiently using a segment tree.
For details of implementation please refer to the solutions attached.
TIME COMPLEXITY:
O(Nlog(N)) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define all(v) v.begin(),v.end()
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using muloset=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=500500;
vector<ll> value(MAX);
vector<vector<ll>> adj;
vector<multiset<ll>> track(MAX);
void dfs(ll cur,ll par){
for(auto chld:adj[cur]){
if(chld!=par){
dfs(chld,cur);
if(track[chld].size()>track[cur].size()){
swap(track[chld],track[cur]);
}
for(auto i:track[chld]){
track[cur].insert(i);
}
}
}
if(track[cur].empty()){
track[cur].insert(value[cur]);
}
else{
auto fs=track[cur].begin();
ll val=*fs;
if(val<value[cur]){
track[cur].erase(fs);
track[cur].insert(value[cur]);
}
}
}
void solve(){
ll n; cin>>n;
ll sum=0;
vector<pair<ll,pair<ll,ll>>> segments;
adj.clear(); adj.resize(2*n+5);
for(ll i=1;i<=n;i++){
ll l,r,v; cin>>l>>r>>v;
sum+=v;
segments.pb({l,{-r,v}});
segments.pb({i,{-i,0}});
}
sort(all(segments));
ll pos=2;
vector<pair<ll,ll>> prv; prv.pb({n,1});
value[1]=0;
for(auto it:segments){
while(!prv.empty()){
auto i=prv.back();
if(i.f<it.f){
prv.pop_back();
}
else{
break;
}
}
ll par=(prv.back()).s;
adj[par].pb(pos);
value[pos]=it.s.s;
prv.pb({-it.s.f,pos++});
}
dfs(1,0);
ll ans=0;
for(auto it:track[1]){
ans+=it;
}
for(ll i=1;i<=2*n;i++){
track[i].clear();
}
cout<<ans<<nline;
cerr<<sum<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(15);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Tester-1's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Point-update Segment Tree
* Source: kactl
* Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
* f is any associative function.
* Time: O(logn) update/query
*/
struct Node {
int mn = INT_MAX, pos = INT_MAX;
};
Node unit;
template<class T>
struct SegTree {
T f(T a, T b) {
if (b.mn > a.mn) b = a;
return b;
}
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, int val) {
pos += n;
s[pos] = {val, pos-n};
while (pos /= 2) s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<array<int, 3>> segments(n);
for (auto &[L, R, x] : segments) cin >> L >> R >> x;
sort(begin(segments), end(segments), [](auto a, auto b) {
return a[1] - a[0] < b[1] - b[0];
});
SegTree<Node> T(n+1);
for (int i = 1; i <= n; ++i) T.update(i, 0);
ll ans = 0;
for (auto [L, R, x] : segments) {
auto res = T.query(L, R+1);
if (res.mn < x) {
ans += x - res.mn;
T.update(res.pos, x);
}
}
cout << ans << '\n';
}
}
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;
using ii = pair<ll,ll>;
set<int> gs;
vector<multiset<ll> > vz;
multiset<ll> dfs(int c, vector<vector<int> >&g, vector<pair<int,int> >&v, vector<ll> &val){
multiset<ll> tmp, z;
for(auto h:g[c]){
tmp = dfs(h,g,v,val);
if(tmp.size()>z.size()) z.swap(tmp);
for(auto h1:tmp) z.insert(h1);
}
auto it = gs.lower_bound(v[c].ff);
if(it!=gs.end() && *it<=v[c].ss){
gs.erase(it);
z.insert(val[c]);
}
else{
auto it1 = z.begin();
if(*it1<val[c]){
z.erase(it1);
z.insert(val[c]);
}
}
return z;
}
void solve(){
int n = readIntLn(1,1e5);
sum_n += n;
vector<pair<int,int> > v(n+1);
vector<ll> val(n+1);
vector<pair<pair<int,int>,int> > u;
int l,r;
val[0] = 0;
rep_a(i,1,n+1){
l = readIntSp(1,n);
r = readIntSp(1,n);
val[i] = readIntLn(1,1e9);
v[i] = mp(l,r);
u.pb(mp(mp(l,l-r),i));
u.pb(mp(mp(r+1,-1e9),-i));
}
sort(u.begin(), u.end());
int ctr = 0;
for(auto h:u){
if(h.ss>0) ctr++;
else ctr--;
assert(ctr>=0);
}
assert(ctr==0);
vector<vector<int> > g(n+1, vector<int>());
vector<int> stk;
stk.pb(0);
for(auto h:u){
if(h.ss>0){
g[stk.back()].pb(h.ss);
stk.pb(h.ss);
}
else{
stk.pop_back();
}
}
gs.clear();
rep_a(i,1,n+1) gs.insert(i);
// vz.assign(n+1, multiset<ll>());
auto zz = dfs(0,g,v,val);
ll ans = 0;
for(auto h:zz) ans+=h;
cout<<ans<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,1e5);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
assert(sum_n<=3e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}