oj.uz

Submission #423841

# Submission time Handle Problem Language Result Execution time Memory
423841 2021-06-11T13:14:20 Z errorgorn Treatment Project (JOI20_treatment) C++17
4 / 100
 1515 ms 276032 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	set<ii> v;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void ins(int i,ii j){
		v.insert(j);
		
		if (s==e) return;
		if (i<=m) l->ins(i,j);
		else r->ins(i,j);
	}
	
	void rem(int i,ii j){
		v.erase(j);
		
		if (s==e) return;
		if (i<=m) l->rem(i,j);
		else r->rem(i,j);
	}
	
	int query(int i,int j,int k){
		if (s==i && e==j){
			if (v.empty()) return -1;
			
			if ((*v.begin()).fi<=k) return (*v.begin()).se;
			else return -1;
		}
		else if (j<=m) return l->query(i,j,k);
		else if (m<i) return r->query(i,j,k);
		else{
			int temp=l->query(i,m,k);
			if (temp==-1) return r->query(m+1,j,k);
			else return temp;
		}
	}
} *root1=new node(0,100005),*root2=new node(0,100005);

int n,k;

struct E{
	int l,r;
	int t;
	ll cost;
	
	int dt; //discretized time
};
vector<E> v;

struct upd{
	int segno; //which tree
	int i,j,k;
	ll val;
};

struct cmp{
	bool operator () (upd i,upd j){
		return i.val>j.val;
	}
};

priority_queue<upd,vector<upd>,cmp> pq;

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	
	int a,b,c,d;
	rep(x,0,k){
		cin>>a>>b>>c>>d;
		v.pub({b,c+1,a,d});
	}
	
	vector<int> allt;
	rep(x,0,k) allt.pub(v[x].t);
	sort(all(allt));
	allt.erase(unique(all(allt)),allt.end());
	map<int,int> tid;
	rep(x,0,sz(allt)) tid[allt[x]]=x+1;
	rep(x,0,k) v[x].dt=tid[v[x].t];
	
	ll ans=1e18;
	
	rep(x,0,k){
		if (v[x].l==1){
			if (v[x].r==n+1) ans=min(ans,v[x].cost);
			
			pq.push(upd({1,v[x].t,100005,v[x].r+v[x].t,v[x].cost}));
			pq.push(upd({2,0,v[x].t-1,v[x].r-v[x].t,v[x].cost}));
		}
		else{
			root1->ins(v[x].dt,ii(v[x].l+v[x].t,x));
			root2->ins(v[x].dt,ii(v[x].l-v[x].t,x));
		}
	}
	
	while (!pq.empty()){
		upd u=pq.top();
		pq.pop();
		
		if (u.segno==1){
			while (true){
				int x=root1->query(u.i,u.j,u.k);
				if (x==-1) break;
				
				pq.push(upd({1,v[x].t,100005,v[x].r+v[x].t,v[x].cost+u.val}));
				pq.push(upd({2,0,v[x].t-1,v[x].r-v[x].t,v[x].cost+u.val}));
				
				root1->rem(v[x].dt,ii(v[x].l+v[x].t,x));
				root2->rem(v[x].dt,ii(v[x].l-v[x].t,x));
				
				if (v[x].r==n+1) ans=min(ans,v[x].cost+u.val);
			}
		}
		else{
			while (true){
				int x=root2->query(u.i,u.j,u.k);
				if (x==-1) break;
				
				pq.push(upd({1,v[x].t,100005,v[x].r+v[x].t,v[x].cost+u.val}));
				pq.push(upd({2,0,v[x].t-1,v[x].r-v[x].t,v[x].cost+u.val}));
				
				root1->rem(v[x].dt,ii(v[x].l+v[x].t,x));
				root2->rem(v[x].dt,ii(v[x].l-v[x].t,x));
				
				if (v[x].r==n+1) ans=min(ans,v[x].cost+u.val);
			}
		}
	}
	
	if (ans==1e18) cout<<"-1"<<endl;
	else cout<<ans<<endl;
}

Compilation message

treatment.cpp: In constructor 'node::node(int, int)':
treatment.cpp:27:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1230 ms 266768 KB Output is correct
2 Correct 947 ms 266744 KB Output is correct
3 Correct 985 ms 214356 KB Output is correct
4 Correct 1111 ms 214364 KB Output is correct
5 Correct 1282 ms 273808 KB Output is correct
6 Correct 1214 ms 267312 KB Output is correct
7 Correct 1165 ms 266836 KB Output is correct
8 Correct 782 ms 264596 KB Output is correct
9 Correct 756 ms 266544 KB Output is correct
10 Correct 670 ms 266832 KB Output is correct
11 Correct 1428 ms 276012 KB Output is correct
12 Correct 1342 ms 275856 KB Output is correct
13 Correct 1389 ms 276032 KB Output is correct
14 Correct 1387 ms 275856 KB Output is correct
15 Correct 1515 ms 266952 KB Output is correct
16 Correct 1360 ms 266680 KB Output is correct
17 Correct 1429 ms 266912 KB Output is correct
18 Correct 1479 ms 275992 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 76544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 76544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1230 ms 266768 KB Output is correct
2 Correct 947 ms 266744 KB Output is correct
3 Correct 985 ms 214356 KB Output is correct
4 Correct 1111 ms 214364 KB Output is correct
5 Correct 1282 ms 273808 KB Output is correct
6 Correct 1214 ms 267312 KB Output is correct
7 Correct 1165 ms 266836 KB Output is correct
8 Correct 782 ms 264596 KB Output is correct
9 Correct 756 ms 266544 KB Output is correct
10 Correct 670 ms 266832 KB Output is correct
11 Correct 1428 ms 276012 KB Output is correct
12 Correct 1342 ms 275856 KB Output is correct
13 Correct 1389 ms 276032 KB Output is correct
14 Correct 1387 ms 275856 KB Output is correct
15 Correct 1515 ms 266952 KB Output is correct
16 Correct 1360 ms 266680 KB Output is correct
17 Correct 1429 ms 266912 KB Output is correct
18 Correct 1479 ms 275992 KB Output is correct
19 Runtime error 96 ms 76544 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -