oj.uz

Submission #676891

# Submission time Handle Problem Language Result Execution time Memory
676891 2023-01-01T13:15:11 Z alvingogo Treatment Project (JOI20_treatment) C++14
4 / 100
 93 ms 9808 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1,1e18);
	}
	void update(int x,int y){
		x++;
		for(;x;x-=(x&-x)){
			bt[x]=min(bt[x],y);
		}
	}
	int query(int x){
		x++;
		int ans=1e18;
		for(;x<=n;x+=(x&-x)){
			ans=min(ans,bt[x]);
		}
		return ans;
	}
};
struct qu{
	int t,l,r,c;
};
vector<qu> v;
bool cmp(qu a,qu b){
	return a.t<b.t;
}
bool cmp2(qu a,qu b){
	return a.l<b.l;
}
signed main(){
    AquA;
	int n,m;
	cin >> n >> m;
	v.resize(m);
	for(int i=0;i<m;i++){
		cin >> v[i].t >> v[i].l >> v[i].r >> v[i].c;
		v[i].l--;
		v[i].r--;
	}
	sort(v.begin(),v.end(),cmp);
	int nw=1;
	int ans=1e18;
	for(int i=0;i<m;i++){
		if(i==m-1 || v[i].t!=v[i+1].t){
			int uu=v[i].t-nw;
			nw=v[i].t;
			vector<int> gg;
			for(int j=0;j<=i;j++){
				if(v[i].t!=v[j].t){
					v[j].l+=uu;
					v[j].r-=uu;
				}
				if(v[j].l>v[j].r){
					continue;
				}
				gg.push_back(v[j].l-1);
				gg.push_back(v[j].r);
			}	
			gg.push_back(0);
			gg.push_back(n-1);
			sort(gg.begin(),gg.end());
			gg.erase(unique(gg.begin(),gg.end()),gg.end());
			BIT bt;
			bt.init(gg.size());
			bt.update(0,0);
			sort(v.begin(),v.begin()+i+1,cmp2);
			for(int j=0;j<=i;j++){
				//cout << v[j].t << " " << v[j].l << " " << v[j].r << "\n";
			}
			for(int j=0;j<=i;j++){
				if(v[j].l<=v[j].r){
					int a=lower_bound(gg.begin(),gg.end(),v[j].l-1)-gg.begin();
					int x=bt.query(a);
					int y=lower_bound(gg.begin(),gg.end(),v[j].r)-gg.begin();
					bt.update(y,v[j].c+x);
					//cout << i << " " << a << " " << x << " " << y << "\n";
				} 	
			}
			ans=min(ans,bt.query(gg.size()-1));
		}
	}
	if(ans>5e17){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5792 KB Output is correct
2 Correct 82 ms 5740 KB Output is correct
3 Correct 70 ms 7824 KB Output is correct
4 Correct 74 ms 7784 KB Output is correct
5 Correct 58 ms 8708 KB Output is correct
6 Correct 68 ms 8672 KB Output is correct
7 Correct 65 ms 8684 KB Output is correct
8 Correct 57 ms 8688 KB Output is correct
9 Correct 60 ms 8688 KB Output is correct
10 Correct 68 ms 8628 KB Output is correct
11 Correct 84 ms 9460 KB Output is correct
12 Correct 84 ms 9432 KB Output is correct
13 Correct 88 ms 9700 KB Output is correct
14 Correct 86 ms 9712 KB Output is correct
15 Correct 92 ms 9696 KB Output is correct
16 Correct 93 ms 9808 KB Output is correct
17 Correct 85 ms 9028 KB Output is correct
18 Correct 79 ms 8680 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5792 KB Output is correct
2 Correct 82 ms 5740 KB Output is correct
3 Correct 70 ms 7824 KB Output is correct
4 Correct 74 ms 7784 KB Output is correct
5 Correct 58 ms 8708 KB Output is correct
6 Correct 68 ms 8672 KB Output is correct
7 Correct 65 ms 8684 KB Output is correct
8 Correct 57 ms 8688 KB Output is correct
9 Correct 60 ms 8688 KB Output is correct
10 Correct 68 ms 8628 KB Output is correct
11 Correct 84 ms 9460 KB Output is correct
12 Correct 84 ms 9432 KB Output is correct
13 Correct 88 ms 9700 KB Output is correct
14 Correct 86 ms 9712 KB Output is correct
15 Correct 92 ms 9696 KB Output is correct
16 Correct 93 ms 9808 KB Output is correct
17 Correct 85 ms 9028 KB Output is correct
18 Correct 79 ms 8680 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -