oj.uz

Submission #217739

# Submission time Handle Problem Language Result Execution time Memory
217739 2020-03-30T14:55:37 Z _7_7_ Treatment Project (JOI20_treatment) C++14
39 / 100
 3000 ms 211696 KB 
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef unsigned long long ull;
typedef pair < int, int > pii;
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


ll d[N];
vi xx, toDel;
int n, m, x[N];
set < pii > T[N << 2][2];
set < pair < ll, int > > q;


struct project {
    ll c;
	int t, l, r;
} a[N];

void add (int pos, int lvl, pii x, int v = 1, int tl = 0, int tr = m - 1) {
	T[v][lvl].insert(x);
	if (tl == tr)
		return;

	int tm = (tl + tr) >> 1;
	if (pos <= tm)
		add(pos, lvl, x, v << 1, tl, tm);
	else
		add(pos, lvl, x, v << 1 | 1, tm + 1, tr);
}

void del (int pos, int lvl, pii x, int v = 1, int tl = 0, int tr = m - 1) {
	T[v][lvl].erase(x);
	if (tl == tr)
		return;
	
	int tm = (tl + tr) >> 1;
	if (pos <= tm)
		del(pos, lvl, x, v << 1, tl, tm);
	else
		del(pos, lvl, x, v << 1 | 1, tm + 1, tr);
}

void f (int l, int r, int lvl, int X, ll Y, int v = 1, int tl = 0, int tr = m - 1) {
	if (l > r || l > tr || tl > r)
		return;

	if (l <= tl && tr <= r) {		
		auto it = T[v][lvl].begin();            
		while (it != T[v][lvl].end()  && it->f <= X) {
			toDel.pb(it->s);
			++it;
		}

		while (sz(toDel)) {
		    int i = toDel.back();
		    toDel.ppb();
		    
			d[i] = Y + a[i].c;
			q.insert({d[i], i});
			del(x[i], 0, {a[i].l + a[i].t, i});
			del(x[i], 1, {a[i].l - a[i].t, i});
		}
		return;
	}

	int tm = (tl + tr) >> 1;
	f(l, r, lvl, X, Y, v << 1, tl, tm);
	f(l, r, lvl, X, Y, v << 1 | 1, tm + 1, tr);
}
	


main () {
    memset(d, -1, sizeof(d));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d%lld", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
		++a[i].r;
		xx.pb(a[i].t);
	}
	
	sort(all(xx));
	xx.resize(unique(all(xx)) - xx.begin());
	
    for (int i = 1; i <= m; ++i) {
        x[i] = lower_bound(all(xx), a[i].t) - xx.begin();
        if (a[i].l == 1) {
            d[i] = a[i].c;
            q.insert({d[i], i});
        } else {
            add(x[i], 0, {a[i].l + a[i].t, i});
            add(x[i], 1, {a[i].l - a[i].t, i});
        }        
    }


	while (sz(q)) {
		int v = q.begin()->s;
		q.erase(q.begin());
		
		f(x[v], m - 1, 0, a[v].r + a[v].t, d[v]);
		f(0, x[v], 1, a[v].r - a[v].t, d[v]);
	}
	
		
	ll mn = INF;	
	for (int i = 1; i <= m; ++i)
		if (a[i].r == n + 1 && d[i] > -1)
			mn = min(mn, d[i]);

	if (mn == INF)
		mn = -1;
	printf("%lld\n", mn);
}

Compilation message

treatment.cpp:105:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
treatment.cpp: In function 'int main()':
treatment.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%lld", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 210944 KB Output is correct
2 Correct 1174 ms 210924 KB Output is correct
3 Correct 928 ms 170448 KB Output is correct
4 Correct 924 ms 170480 KB Output is correct
5 Correct 1139 ms 209508 KB Output is correct
6 Correct 970 ms 210904 KB Output is correct
7 Correct 886 ms 210876 KB Output is correct
8 Correct 1118 ms 209308 KB Output is correct
9 Correct 1034 ms 210752 KB Output is correct
10 Correct 1018 ms 210884 KB Output is correct
11 Correct 1156 ms 211672 KB Output is correct
12 Correct 1194 ms 211196 KB Output is correct
13 Correct 1198 ms 211132 KB Output is correct
14 Correct 1149 ms 210972 KB Output is correct
15 Correct 1060 ms 211056 KB Output is correct
16 Correct 1055 ms 211004 KB Output is correct
17 Correct 1016 ms 211056 KB Output is correct
18 Correct 1130 ms 211696 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38648 KB Output is correct
2 Correct 26 ms 38656 KB Output is correct
3 Correct 26 ms 38656 KB Output is correct
4 Correct 26 ms 38656 KB Output is correct
5 Correct 26 ms 38784 KB Output is correct
6 Correct 27 ms 38656 KB Output is correct
7 Correct 26 ms 38656 KB Output is correct
8 Correct 26 ms 38656 KB Output is correct
9 Correct 27 ms 38656 KB Output is correct
10 Correct 27 ms 38656 KB Output is correct
11 Correct 26 ms 38656 KB Output is correct
12 Correct 27 ms 38656 KB Output is correct
13 Correct 26 ms 38656 KB Output is correct
14 Correct 26 ms 38656 KB Output is correct
15 Correct 27 ms 38656 KB Output is correct
16 Correct 26 ms 38784 KB Output is correct
17 Correct 27 ms 38656 KB Output is correct
18 Correct 27 ms 38656 KB Output is correct
19 Correct 27 ms 38648 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38648 KB Output is correct
2 Correct 26 ms 38656 KB Output is correct
3 Correct 26 ms 38656 KB Output is correct
4 Correct 26 ms 38656 KB Output is correct
5 Correct 26 ms 38784 KB Output is correct
6 Correct 27 ms 38656 KB Output is correct
7 Correct 26 ms 38656 KB Output is correct
8 Correct 26 ms 38656 KB Output is correct
9 Correct 27 ms 38656 KB Output is correct
10 Correct 27 ms 38656 KB Output is correct
11 Correct 26 ms 38656 KB Output is correct
12 Correct 27 ms 38656 KB Output is correct
13 Correct 26 ms 38656 KB Output is correct
14 Correct 26 ms 38656 KB Output is correct
15 Correct 27 ms 38656 KB Output is correct
16 Correct 26 ms 38784 KB Output is correct
17 Correct 27 ms 38656 KB Output is correct
18 Correct 27 ms 38656 KB Output is correct
19 Correct 27 ms 38648 KB Output is correct
20 Correct 62 ms 43640 KB Output is correct
21 Correct 72 ms 43640 KB Output is correct
22 Correct 74 ms 45048 KB Output is correct
23 Correct 74 ms 45048 KB Output is correct
24 Correct 66 ms 44152 KB Output is correct
25 Correct 71 ms 45048 KB Output is correct
26 Correct 66 ms 45048 KB Output is correct
27 Correct 69 ms 45056 KB Output is correct
28 Correct 68 ms 44280 KB Output is correct
29 Correct 67 ms 45048 KB Output is correct
30 Correct 54 ms 45048 KB Output is correct
31 Correct 57 ms 45048 KB Output is correct
32 Correct 78 ms 45048 KB Output is correct
33 Correct 95 ms 45048 KB Output is correct
34 Correct 81 ms 45176 KB Output is correct
35 Correct 79 ms 45176 KB Output is correct
36 Correct 75 ms 45176 KB Output is correct
37 Correct 76 ms 45048 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 210944 KB Output is correct
2 Correct 1174 ms 210924 KB Output is correct
3 Correct 928 ms 170448 KB Output is correct
4 Correct 924 ms 170480 KB Output is correct
5 Correct 1139 ms 209508 KB Output is correct
6 Correct 970 ms 210904 KB Output is correct
7 Correct 886 ms 210876 KB Output is correct
8 Correct 1118 ms 209308 KB Output is correct
9 Correct 1034 ms 210752 KB Output is correct
10 Correct 1018 ms 210884 KB Output is correct
11 Correct 1156 ms 211672 KB Output is correct
12 Correct 1194 ms 211196 KB Output is correct
13 Correct 1198 ms 211132 KB Output is correct
14 Correct 1149 ms 210972 KB Output is correct
15 Correct 1060 ms 211056 KB Output is correct
16 Correct 1055 ms 211004 KB Output is correct
17 Correct 1016 ms 211056 KB Output is correct
18 Correct 1130 ms 211696 KB Output is correct
19 Correct 26 ms 38648 KB Output is correct
20 Correct 26 ms 38656 KB Output is correct
21 Correct 26 ms 38656 KB Output is correct
22 Correct 26 ms 38656 KB Output is correct
23 Correct 26 ms 38784 KB Output is correct
24 Correct 27 ms 38656 KB Output is correct
25 Correct 26 ms 38656 KB Output is correct
26 Correct 26 ms 38656 KB Output is correct
27 Correct 27 ms 38656 KB Output is correct
28 Correct 27 ms 38656 KB Output is correct
29 Correct 26 ms 38656 KB Output is correct
30 Correct 27 ms 38656 KB Output is correct
31 Correct 26 ms 38656 KB Output is correct
32 Correct 26 ms 38656 KB Output is correct
33 Correct 27 ms 38656 KB Output is correct
34 Correct 26 ms 38784 KB Output is correct
35 Correct 27 ms 38656 KB Output is correct
36 Correct 27 ms 38656 KB Output is correct
37 Correct 27 ms 38648 KB Output is correct
38 Correct 62 ms 43640 KB Output is correct
39 Correct 72 ms 43640 KB Output is correct
40 Correct 74 ms 45048 KB Output is correct
41 Correct 74 ms 45048 KB Output is correct
42 Correct 66 ms 44152 KB Output is correct
43 Correct 71 ms 45048 KB Output is correct
44 Correct 66 ms 45048 KB Output is correct
45 Correct 69 ms 45056 KB Output is correct
46 Correct 68 ms 44280 KB Output is correct
47 Correct 67 ms 45048 KB Output is correct
48 Correct 54 ms 45048 KB Output is correct
49 Correct 57 ms 45048 KB Output is correct
50 Correct 78 ms 45048 KB Output is correct
51 Correct 95 ms 45048 KB Output is correct
52 Correct 81 ms 45176 KB Output is correct
53 Correct 79 ms 45176 KB Output is correct
54 Correct 75 ms 45176 KB Output is correct
55 Correct 76 ms 45048 KB Output is correct
56 Correct 1661 ms 168236 KB Output is correct
57 Correct 1616 ms 168144 KB Output is correct
58 Correct 1779 ms 207344 KB Output is correct
59 Correct 1788 ms 207280 KB Output is correct
60 Correct 2053 ms 208016 KB Output is correct
61 Correct 1768 ms 207340 KB Output is correct
62 Correct 1595 ms 168264 KB Output is correct
63 Correct 1518 ms 207896 KB Output is correct
64 Correct 1520 ms 208108 KB Output is correct
65 Correct 1197 ms 210928 KB Output is correct
66 Correct 1973 ms 208116 KB Output is correct
67 Correct 2379 ms 206520 KB Output is correct
68 Correct 1967 ms 208092 KB Output is correct
69 Correct 1632 ms 208108 KB Output is correct
70 Correct 2586 ms 206852 KB Output is correct
71 Correct 2021 ms 207984 KB Output is correct
72 Correct 1612 ms 207984 KB Output is correct
73 Correct 2634 ms 206980 KB Output is correct
74 Correct 1325 ms 207832 KB Output is correct
75 Correct 1195 ms 207984 KB Output is correct
76 Execution timed out 3086 ms 208976 KB Time limit exceeded
77 Halted 0 ms 0 KB -