Submission #1040474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040474		prabhu_2020	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	0 ms	344 KiB

arranging_tickets

/*	WHY NOT ?	*/
// #pragma GCC target("popcnt")
#include <bits/stdc++.h> 
using namespace std; 
using namespace std::chrono;
#define endl '\n'
#define mn first
#define mnc second

#define int long long

int MAX = 1e5;
int MAXN = 2 * MAX + 2;
vector<pair<int,int>> tree;
vector<int> lazy;

// pair<int,int> tree[4 * MAXN];
// int lazy[4 * MAXN];

pair<long long, long long> merge(pair<long long, long long> a,
                                 pair<long long, long long> b) {
	if (a.first < b.first) { return a; }
	if (a.first > b.first) { return b; }
	return {a.first, a.second + b.second};
}

void push(int node,int ss,int se){
	if(lazy[node] != 0){
		tree[node].mn += lazy[node];
		if(ss != se){
			lazy[2 *node] += lazy[node];
			lazy[2 *node + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}
void build(int node,int ss,int se){
	if(ss == se){
		tree[node].mn = 0;
		tree[node].mnc = 1;
		lazy[node] = 0;
		return;
	}
	int mid = (ss + se) / 2;
	build(2 * node,ss,mid);
	build(2 * node + 1,mid + 1,se);
	tree[node] = merge(tree[2*node],tree[2*node+1]);
}
void update(int l,int r,int v,int node,int ss = 0,int se = MAXN - 1){
	if(l > r)	return;
	if(ss > r || se < l)return ;
	push(node,ss,se);	
	if(ss >= l && se <= r){
		tree[node].mn += v;
		if(ss != se){
			lazy[2 * node] += v;
			lazy[2 * node + 1] += v;	
		}
		return ;
	}
	int mid = (ss + se) / 2;
	update(l,r,v,2 * node,ss,mid);
	update(l,r,v,2 * node + 1,mid + 1,se);
	push(2 * node,ss,mid);	
	push(2 * node + 1,mid + 1,se);	
	tree[node] = merge(tree[2*node],tree[2*node + 1]);
}
pair<int,int> query(int  node,int ss,int se,int l,int r){
	if(ss > r || se < l){
		pair<int,int> ret;
		ret.first = 1e9;
		ret.second = 1;
		return ret;
	}
	push(node,ss,se);
	if(ss >= l && se <= r){
		return tree[node];
	}
	int mid = (ss + se) / 2;
	pair<int,int> lft = query(2 * node,ss,mid,l,r);
	pair<int,int> rgt = query(2 * node + 1,mid + 1,se,l,r);
	push(2 * node,ss,mid);	
	push(2 * node + 1,mid + 1,se);	
	pair<int,int> ans = merge(lft,rgt);
	return ans;
}
 /* more_precisely [ total elements  - #(min_elements)] */
 /* return number of non - zero elements */
 
int query(){
	return MAXN - query(1,0,MAXN-1,0,MAXN-1).mnc;
}
/* build(1,0,MAXN-1); */

void solve(){
	/* https://www.youtube.com/watch?v=iMjd2QI6NEs*/
	/* refer for solution */
	int n,m;
	cin>>n>>m;
	MAXN = n + 1;
	tree = vector<pair<int,int>> (4 * MAXN);
	lazy = vector<int> (4 * MAXN,0);
	build(1,0,MAXN - 1);
	vector<pair<int,int>> p(m);
	vector<int> c(m,0);
	for(int i=0;i<m;i++){
		cin>>p[i].first>>p[i].second;
		cin>>c[i];
		p[i].first--;
		p[i].second--;
		update(p[i].first,p[i].second-1,1,1);
	}
	vector<vector<int>> start(n + 1),end(n + 1);
	for(int i=0;i<m;i++){
		start[p[i].first].push_back(i);
		end[p[i].second].push_back(i);
	}
	int ans = query();
	for(int i=0;i<n;i++){
		for(auto j : start[i]){
			update(p[j].first,p[j].second-1,-1,1);
			update(0,p[j].first - 1,1,1);
			update(p[j].second,n-1,1,1);
		}
		for(auto j:end[i]){
			update(p[j].first,p[j].second-1,1,1);
			update(0,p[j].first-1,-1,1);
			update(p[j].second,n-1,-1,1);
		}
		ans = min(ans,query());
	}
	cout<<ans<<endl;
}
signed main(){
	auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int t = 1; 
	// cin >> t;
	while(t--){
		solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-6 << " miliseconds.\n"; 
    return 0;
}

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