oj.uz

Submission #217740

# Submission time Handle Problem Language Result Execution time Memory
217740 2020-03-30T15:04:43 Z _7_7_ Treatment Project (JOI20_treatment) C++14
39 / 100
 3000 ms 208112 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 = sz(xx) - 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 = sz(xx) - 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 = sz(xx) - 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 177 ms 51184 KB Output is correct
2 Correct 166 ms 51184 KB Output is correct
3 Correct 193 ms 50672 KB Output is correct
4 Correct 192 ms 50800 KB Output is correct
5 Correct 209 ms 51184 KB Output is correct
6 Correct 156 ms 51312 KB Output is correct
7 Correct 146 ms 51312 KB Output is correct
8 Correct 122 ms 51184 KB Output is correct
9 Correct 120 ms 51184 KB Output is correct
10 Correct 108 ms 51184 KB Output is correct
11 Correct 277 ms 52076 KB Output is correct
12 Correct 266 ms 51824 KB Output is correct
13 Correct 259 ms 51440 KB Output is correct
14 Correct 260 ms 51564 KB Output is correct
15 Correct 220 ms 51312 KB Output is correct
16 Correct 211 ms 51312 KB Output is correct
17 Correct 202 ms 51384 KB Output is correct
18 Correct 244 ms 51952 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 38656 KB Output is correct
2 Correct 27 ms 38656 KB Output is correct
3 Correct 27 ms 38656 KB Output is correct
4 Correct 30 ms 38776 KB Output is correct
5 Correct 26 ms 38656 KB Output is correct
6 Correct 26 ms 38656 KB Output is correct
7 Correct 26 ms 38656 KB Output is correct
8 Correct 28 ms 38656 KB Output is correct
9 Correct 27 ms 38656 KB Output is correct
10 Correct 26 ms 38656 KB Output is correct
11 Correct 27 ms 38656 KB Output is correct
12 Correct 26 ms 38656 KB Output is correct
13 Correct 27 ms 38656 KB Output is correct
14 Correct 27 ms 38656 KB Output is correct
15 Correct 26 ms 38656 KB Output is correct
16 Correct 27 ms 38656 KB Output is correct
17 Correct 27 ms 38656 KB Output is correct
18 Correct 27 ms 38656 KB Output is correct
19 Correct 26 ms 38656 KB Output is correct
20 Correct 58 ms 43260 KB Output is correct
21 Correct 57 ms 43256 KB Output is correct
22 Correct 62 ms 43512 KB Output is correct
23 Correct 60 ms 43516 KB Output is correct
24 Correct 66 ms 44152 KB Output is correct
25 Correct 69 ms 45048 KB Output is correct
26 Correct 71 ms 45176 KB Output is correct
27 Correct 65 ms 45176 KB Output is correct
28 Correct 65 ms 44160 KB Output is correct
29 Correct 66 ms 45048 KB Output is correct
30 Correct 55 ms 45048 KB Output is correct
31 Correct 61 ms 45224 KB Output is correct
32 Correct 80 ms 45176 KB Output is correct
33 Correct 77 ms 45048 KB Output is correct
34 Correct 74 ms 44792 KB Output is correct
35 Correct 79 ms 45048 KB Output is correct
36 Correct 77 ms 45304 KB Output is correct
37 Correct 74 ms 44792 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 51184 KB Output is correct
2 Correct 166 ms 51184 KB Output is correct
3 Correct 193 ms 50672 KB Output is correct
4 Correct 192 ms 50800 KB Output is correct
5 Correct 209 ms 51184 KB Output is correct
6 Correct 156 ms 51312 KB Output is correct
7 Correct 146 ms 51312 KB Output is correct
8 Correct 122 ms 51184 KB Output is correct
9 Correct 120 ms 51184 KB Output is correct
10 Correct 108 ms 51184 KB Output is correct
11 Correct 277 ms 52076 KB Output is correct
12 Correct 266 ms 51824 KB Output is correct
13 Correct 259 ms 51440 KB Output is correct
14 Correct 260 ms 51564 KB Output is correct
15 Correct 220 ms 51312 KB Output is correct
16 Correct 211 ms 51312 KB Output is correct
17 Correct 202 ms 51384 KB Output is correct
18 Correct 244 ms 51952 KB Output is correct
19 Correct 30 ms 38656 KB Output is correct
20 Correct 27 ms 38656 KB Output is correct
21 Correct 27 ms 38656 KB Output is correct
22 Correct 30 ms 38776 KB Output is correct
23 Correct 26 ms 38656 KB Output is correct
24 Correct 26 ms 38656 KB Output is correct
25 Correct 26 ms 38656 KB Output is correct
26 Correct 28 ms 38656 KB Output is correct
27 Correct 27 ms 38656 KB Output is correct
28 Correct 26 ms 38656 KB Output is correct
29 Correct 27 ms 38656 KB Output is correct
30 Correct 26 ms 38656 KB Output is correct
31 Correct 27 ms 38656 KB Output is correct
32 Correct 27 ms 38656 KB Output is correct
33 Correct 26 ms 38656 KB Output is correct
34 Correct 27 ms 38656 KB Output is correct
35 Correct 27 ms 38656 KB Output is correct
36 Correct 27 ms 38656 KB Output is correct
37 Correct 26 ms 38656 KB Output is correct
38 Correct 58 ms 43260 KB Output is correct
39 Correct 57 ms 43256 KB Output is correct
40 Correct 62 ms 43512 KB Output is correct
41 Correct 60 ms 43516 KB Output is correct
42 Correct 66 ms 44152 KB Output is correct
43 Correct 69 ms 45048 KB Output is correct
44 Correct 71 ms 45176 KB Output is correct
45 Correct 65 ms 45176 KB Output is correct
46 Correct 65 ms 44160 KB Output is correct
47 Correct 66 ms 45048 KB Output is correct
48 Correct 55 ms 45048 KB Output is correct
49 Correct 61 ms 45224 KB Output is correct
50 Correct 80 ms 45176 KB Output is correct
51 Correct 77 ms 45048 KB Output is correct
52 Correct 74 ms 44792 KB Output is correct
53 Correct 79 ms 45048 KB Output is correct
54 Correct 77 ms 45304 KB Output is correct
55 Correct 74 ms 44792 KB Output is correct
56 Correct 1518 ms 161112 KB Output is correct
57 Correct 1516 ms 161140 KB Output is correct
58 Correct 1677 ms 198184 KB Output is correct
59 Correct 1749 ms 198092 KB Output is correct
60 Correct 1744 ms 176956 KB Output is correct
61 Correct 1684 ms 197872 KB Output is correct
62 Correct 1523 ms 161312 KB Output is correct
63 Correct 1543 ms 208112 KB Output is correct
64 Correct 1515 ms 207984 KB Output is correct
65 Correct 325 ms 60708 KB Output is correct
66 Correct 1728 ms 176880 KB Output is correct
67 Correct 2387 ms 206516 KB Output is correct
68 Correct 1956 ms 207728 KB Output is correct
69 Correct 1623 ms 206832 KB Output is correct
70 Correct 2637 ms 206956 KB Output is correct
71 Correct 2032 ms 207908 KB Output is correct
72 Correct 1576 ms 208112 KB Output is correct
73 Correct 2624 ms 206960 KB Output is correct
74 Correct 1348 ms 207860 KB Output is correct
75 Correct 1189 ms 207980 KB Output is correct
76 Execution timed out 3040 ms 201640 KB Time limit exceeded
77 Halted 0 ms 0 KB -