oj.uz

Submission #295310

# Submission time Handle Problem Language Result Execution time Memory
295310 2020-09-09T15:29:58 Z 임성재(#5809) Treatment Project (JOI20_treatment) C++17
0 / 100
 174 ms 10600 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;


int n, m;
int t[100010];
int l[100010];
int r[100010];
int c[100010];

vector<int> com;
vector<int> v;

ll dp[300010];
ll tree[1200010];

void update(int node, int s, int e, int i) {
	if(s == e) {
		tree[node] = dp[i];
		return;
	}

	int m = s + e >> 1;

	if(i <= m) update(node*2, s, m, i);
	else update(node*2+1, m+1, e, i);

	tree[node] = min(tree[node*2], tree[node*2+1]);
}

ll cal(int node, int s, int e, int l, int r) {
	if(r < s || e < l) return INF;
	if(l <= s && e <= r) return tree[node];

	return min(cal(node*2, s, (s+e)/2, l, r), cal(node*2+1, (s+e)/2+1, e, l, r));
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<m; i++) {
		cin >> t[i] >> l[i] >> r[i] >> c[i];

		v.eb(i);
		com.eb(l[i]-1);
		com.eb(l[i]);
		com.eb(r[i]);
	}

	com.eb(0);
	com.eb(n);

	sort(all(com));
	com.erase(unique(all(com)), com.end());

	sort(all(v), [&] (int i, int j) {
		return r[i] < r[j];
	});

	for(int i=1; i<com.size(); i++)
		dp[i] = INF, update(1, 0, com.size()-1, i);

	for(auto i : v) {
		r[i] = lower_bound(all(com), r[i]) - com.begin();
		l[i] = lower_bound(all(com), l[i]) - com.begin();

		dp[r[i]] = min(dp[r[i]], cal(1, 0, com.size()-1, l[i]-1, r[i]) + c[i]);
		update(1, 0, com.size()-1, r[i]);
	}

	cout << dp[com.size()-1];
}

Compilation message

treatment.cpp: In function 'void update(int, int, int, int)':
treatment.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int m = s + e >> 1;
      |          ~~^~~
treatment.cpp: In function 'int main()':
treatment.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i=1; i<com.size(); i++)
      |               ~^~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

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