oj.uz

Submission #216794

# Submission time Handle Problem Language Result Execution time Memory
216794 2020-03-28T04:35:46 Z abacaba Treatment Project (JOI20_treatment) C++14
4 / 100
 260 ms 524292 KB 
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
	return uniform_int_distribution <T>(l, r)(rng);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const int mod = 1e9 + 7;
const ll inf = 2e18;
const int N = 1e5 + 15;
int n, m;
ll ans = -1;
 
vector <int> compress;
int sz;
 
ll d[N];
 
priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater <pair <ll, int>>> q;
 
inline int gt(int x) {
	return lower_bound(compress.begin(), compress.end(), x) - compress.begin() + 1;
}
 
struct pt {
	int t, l, r, c;
} a[N];
 
struct segment_tree {
	vector <pii> t[N << 2];
	void build(int v, int tl, int tr) {
		if(tl == tr) {
			if(!t[v].empty()) {
				sort(t[v].begin(), t[v].end(), [&](pii x, pii y) {
					return x > y;
				});
			}
			return;
		}
		int mid = tl + tr >> 1;
		build(v << 1, tl, tr);
		build(v << 1 | 1, mid + 1, tr);
		if(t[v << 1].empty())
			t[v] = t[v << 1 | 1];
		else if(t[v << 1 | 1].empty())
			t[v] = t[v << 1];
		else {
			merge(t[v << 1].begin(), t[v << 1].end(), t[v << 1 | 1].begin(), t[v << 1 | 1].end(), back_inserter(t[v]));
			if(t[v].empty()) {
				cout << "asdasd" << endl;
				exit(0);
			}
			reverse(t[v].begin(), t[v].end());
		}
	}
	void get(int v, int tl, int tr, int l, int r, int val, ll nw) {
		if(tl > r || tr < l)
			return;
		if(tl >= l && tr <= r) {
			while(!t[v].empty() && t[v].back().f <= val) {
				int i = t[v].back().se;
				if(d[i] > nw + a[i].c)
					q.push(mp(d[i] = nw + a[i].c, i));
				t[v].ppb();
			}
			return;
		}
		int mid = tl + tr >> 1;
		get(v << 1, tl, mid, l, r, val, nw);
		get(v << 1 | 1, mid + 1, tr, l, r, val, nw);
	}
	inline void update(int v, int tl, int tr, int pos, pii val) {
		while(1) {
 
			if(tl == tr) {
				t[v].pb(val);
				return;
			}
 
			int mid = tl + tr >> 1;
			if(pos <= mid)
				v <<= 1, tr = mid;
			else
				v = v << 1 | 1, tl = mid + 1;
		}
	}
} t1, t2;
 
inline int nxt() {
	int x;
	scanf("%d", &x);
	return x;
}
 
main() {
	fill(d, d + N, inf);
	n = nxt(); m = nxt();
	for(int i = 1; i <= m; ++i) {
		a[i].t = nxt(); a[i].l = nxt(); a[i].r = nxt(); a[i].c = nxt();
		compress.pb(a[i].t);
	}
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());
 
	sz = compress.size();
 
	for(int i = 1; i <= m; ++i) {
		--a[i].l;
		if(a[i].l == 0) {
			d[i] = a[i].c;
			q.push({d[i], i});
		}
		t1.update(1, 1, sz, gt(a[i].t), mp(a[i].l + a[i].t, i));
		t2.update(1, 1, sz, gt(a[i].t), mp(a[i].l - a[i].t, i));
	}
	t1.build(1, 1, sz);
	t2.build(1, 1, sz);
	while(!q.empty()) {
		int dist = q.top().f, i = q.top().se;
		q.pop();
		if(dist > d[i])
			continue;
 
		t1.get(1, 1, sz, gt(a[i].t), sz, a[i].r + a[i].t, d[i]);
		t2.get(1, 1, sz, 1, gt(a[i].t), a[i].r - a[i].t, d[i]);
	}
	for(int i = 1; i <= m; ++i) {
		if(a[i].r != n || d[i] == inf)
			continue;
		if(ans == -1 || d[i] < ans)
			ans = d[i];
	}
	cout << ans << endl;
	return 0;
}

Compilation message

treatment.cpp: In member function 'void segment_tree::build(int, int, int)':
treatment.cpp:85:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
treatment.cpp: In member function 'void segment_tree::get(int, int, int, int, int, int, long long int)':
treatment.cpp:113:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
treatment.cpp: In member function 'void segment_tree::update(int, int, int, int, std::pair<int, int>)':
treatment.cpp:125:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = tl + tr >> 1;
              ~~~^~~~
treatment.cpp: At global scope:
treatment.cpp:140:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
treatment.cpp: In function 'int nxt()':
treatment.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &x);
  ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 24300 KB Output is correct
2 Correct 105 ms 24428 KB Output is correct
3 Correct 111 ms 24584 KB Output is correct
4 Correct 109 ms 24204 KB Output is correct
5 Correct 115 ms 25612 KB Output is correct
6 Correct 107 ms 24336 KB Output is correct
7 Correct 101 ms 24300 KB Output is correct
8 Correct 94 ms 24300 KB Output is correct
9 Correct 95 ms 24300 KB Output is correct
10 Correct 93 ms 24328 KB Output is correct
11 Correct 132 ms 25580 KB Output is correct
12 Correct 128 ms 25584 KB Output is correct
13 Correct 130 ms 25616 KB Output is correct
14 Correct 127 ms 25580 KB Output is correct
15 Correct 118 ms 23708 KB Output is correct
16 Correct 129 ms 24432 KB Output is correct
17 Correct 113 ms 24468 KB Output is correct
18 Correct 122 ms 25580 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19840 KB Output is correct
2 Runtime error 260 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19840 KB Output is correct
2 Runtime error 260 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 24300 KB Output is correct
2 Correct 105 ms 24428 KB Output is correct
3 Correct 111 ms 24584 KB Output is correct
4 Correct 109 ms 24204 KB Output is correct
5 Correct 115 ms 25612 KB Output is correct
6 Correct 107 ms 24336 KB Output is correct
7 Correct 101 ms 24300 KB Output is correct
8 Correct 94 ms 24300 KB Output is correct
9 Correct 95 ms 24300 KB Output is correct
10 Correct 93 ms 24328 KB Output is correct
11 Correct 132 ms 25580 KB Output is correct
12 Correct 128 ms 25584 KB Output is correct
13 Correct 130 ms 25616 KB Output is correct
14 Correct 127 ms 25580 KB Output is correct
15 Correct 118 ms 23708 KB Output is correct
16 Correct 129 ms 24432 KB Output is correct
17 Correct 113 ms 24468 KB Output is correct
18 Correct 122 ms 25580 KB Output is correct
19 Correct 16 ms 19840 KB Output is correct
20 Runtime error 260 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -