oj.uz

Submission #675797

# Submission time Handle Problem Language Result Execution time Memory
675797 2022-12-27T22:45:30 Z Victor Osumnjičeni (COCI21_osumnjiceni) C++17
110 / 110
 882 ms 409088 KB 
//#pragma GCC target ("avx,avx2,fma")
//#pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

const int inf = 1e9;

int pos_update;
struct Node {
	Node *l = 0, *r = 0;
	int lo, hi, mset = inf, val = inf;
	Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of -inf
	Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = min(l->val, r->val);
		}
		else val = v[lo];
	}
	int query(const int &L, const int &R) {
		if (R <= lo || hi <= L) return inf;
		if (L <= lo && hi <= R) {
			int prev_val=val;
			val=mset=pos_update;
			return prev_val;
		}
		push();
		val=pos_update;
		return min(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val = x;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = min(l->val, r->val);
		}
	}

	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset != inf)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf;
	}
};

int jmp[18][200005];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n,q;
    int heights[200005][2];
    cin>>n;

	//set<int> unique_heights;
    rep(i,0,n) rep(j,0,2) cin>>heights[i][j];//,unique_heights.insert(heights[i][j]);
	//umap<int,int> compress;
	//int cnt=0;
	//trav(height,unique_heights) compress[height]=cnt++;
	//rep(i,0,n) rep(j,0,2) heights[i][j]=compress[heights[i][j]];
	

    Node segtree(0,INF);
	int min_val=n;
    per(i,0,n) {
		pos_update=i;
        jmp[0][i]=segtree.query(heights[i][0],heights[i][1]+1);
        if(i+1!=n) jmp[0][i]=min(jmp[0][i],jmp[0][i+1]);
        //debug(jmp[0][i])<<endl;
        //segtree.set(heights[i][0],heights[i][1]+1,i);
    }

    rep(j,1,18) rep(i,0,n) {
        if(jmp[j-1][i]>=inf) jmp[j][i]=inf;
        else jmp[j][i]=jmp[j-1][jmp[j-1][i]];
    }

    cin>>q;
    while(q--) {
        int lo,hi;
        cin>>lo>>hi;
        --lo;
        int cnt=1;
        //cout<<"lo = "<<lo<<" hi = "<<hi<<endl;
        per(j,0,18) {
            //cout<<"j = "<<j<<" lo = "<<lo<<" jmp = "<<jmp[j][lo]<<endl;
            if(jmp[j][lo]<hi) {
                cnt+=1<<j;
                lo=jmp[j][lo];
            }
        }
        cout<<cnt<<'\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:97:6: warning: unused variable 'min_val' [-Wunused-variable]
   97 |  int min_val=n;
      |      ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 392020 KB Output is correct
2 Correct 655 ms 387148 KB Output is correct
3 Correct 653 ms 388184 KB Output is correct
4 Correct 679 ms 392076 KB Output is correct
5 Correct 686 ms 406932 KB Output is correct
6 Correct 72 ms 14664 KB Output is correct
7 Correct 74 ms 14940 KB Output is correct
8 Correct 73 ms 15056 KB Output is correct
9 Correct 80 ms 15316 KB Output is correct
10 Correct 78 ms 14856 KB Output is correct
11 Correct 365 ms 209380 KB Output is correct
12 Correct 345 ms 196756 KB Output is correct
13 Correct 363 ms 196308 KB Output is correct
14 Correct 386 ms 209752 KB Output is correct
15 Correct 357 ms 203752 KB Output is correct
16 Correct 1 ms 1876 KB Output is correct
17 Correct 72 ms 15564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16828 KB Output is correct
2 Correct 21 ms 15956 KB Output is correct
3 Correct 19 ms 16084 KB Output is correct
4 Correct 19 ms 16648 KB Output is correct
5 Correct 19 ms 15824 KB Output is correct
6 Correct 4 ms 2260 KB Output is correct
7 Correct 7 ms 2332 KB Output is correct
8 Correct 4 ms 2276 KB Output is correct
9 Correct 5 ms 2260 KB Output is correct
10 Correct 4 ms 2260 KB Output is correct
11 Correct 10 ms 7252 KB Output is correct
12 Correct 9 ms 6836 KB Output is correct
13 Correct 9 ms 6868 KB Output is correct
14 Correct 9 ms 7136 KB Output is correct
15 Correct 11 ms 7252 KB Output is correct
16 Correct 1 ms 1876 KB Output is correct
17 Correct 4 ms 2272 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16828 KB Output is correct
2 Correct 21 ms 15956 KB Output is correct
3 Correct 19 ms 16084 KB Output is correct
4 Correct 19 ms 16648 KB Output is correct
5 Correct 19 ms 15824 KB Output is correct
6 Correct 4 ms 2260 KB Output is correct
7 Correct 7 ms 2332 KB Output is correct
8 Correct 4 ms 2276 KB Output is correct
9 Correct 5 ms 2260 KB Output is correct
10 Correct 4 ms 2260 KB Output is correct
11 Correct 10 ms 7252 KB Output is correct
12 Correct 9 ms 6836 KB Output is correct
13 Correct 9 ms 6868 KB Output is correct
14 Correct 9 ms 7136 KB Output is correct
15 Correct 11 ms 7252 KB Output is correct
16 Correct 1 ms 1876 KB Output is correct
17 Correct 4 ms 2272 KB Output is correct
18 Correct 79 ms 17460 KB Output is correct
19 Correct 74 ms 16876 KB Output is correct
20 Correct 81 ms 17732 KB Output is correct
21 Correct 83 ms 16848 KB Output is correct
22 Correct 75 ms 16572 KB Output is correct
23 Correct 58 ms 3104 KB Output is correct
24 Correct 67 ms 3096 KB Output is correct
25 Correct 62 ms 3120 KB Output is correct
26 Correct 63 ms 3020 KB Output is correct
27 Correct 57 ms 2936 KB Output is correct
28 Correct 48 ms 7244 KB Output is correct
29 Correct 54 ms 7248 KB Output is correct
30 Correct 49 ms 7244 KB Output is correct
31 Correct 51 ms 7160 KB Output is correct
32 Correct 50 ms 7544 KB Output is correct
33 Correct 1 ms 1876 KB Output is correct
34 Correct 48 ms 3276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 407224 KB Output is correct
2 Correct 671 ms 400220 KB Output is correct
3 Correct 648 ms 376284 KB Output is correct
4 Correct 624 ms 373168 KB Output is correct
5 Correct 640 ms 383404 KB Output is correct
6 Correct 74 ms 14680 KB Output is correct
7 Correct 72 ms 14672 KB Output is correct
8 Correct 73 ms 14808 KB Output is correct
9 Correct 79 ms 14668 KB Output is correct
10 Correct 83 ms 15832 KB Output is correct
11 Correct 354 ms 195024 KB Output is correct
12 Correct 384 ms 213644 KB Output is correct
13 Correct 349 ms 194924 KB Output is correct
14 Correct 357 ms 200896 KB Output is correct
15 Correct 379 ms 212696 KB Output is correct
16 Correct 1 ms 1888 KB Output is correct
17 Correct 73 ms 14936 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 392020 KB Output is correct
2 Correct 655 ms 387148 KB Output is correct
3 Correct 653 ms 388184 KB Output is correct
4 Correct 679 ms 392076 KB Output is correct
5 Correct 686 ms 406932 KB Output is correct
6 Correct 72 ms 14664 KB Output is correct
7 Correct 74 ms 14940 KB Output is correct
8 Correct 73 ms 15056 KB Output is correct
9 Correct 80 ms 15316 KB Output is correct
10 Correct 78 ms 14856 KB Output is correct
11 Correct 365 ms 209380 KB Output is correct
12 Correct 345 ms 196756 KB Output is correct
13 Correct 363 ms 196308 KB Output is correct
14 Correct 386 ms 209752 KB Output is correct
15 Correct 357 ms 203752 KB Output is correct
16 Correct 1 ms 1876 KB Output is correct
17 Correct 72 ms 15564 KB Output is correct
18 Correct 19 ms 16828 KB Output is correct
19 Correct 21 ms 15956 KB Output is correct
20 Correct 19 ms 16084 KB Output is correct
21 Correct 19 ms 16648 KB Output is correct
22 Correct 19 ms 15824 KB Output is correct
23 Correct 4 ms 2260 KB Output is correct
24 Correct 7 ms 2332 KB Output is correct
25 Correct 4 ms 2276 KB Output is correct
26 Correct 5 ms 2260 KB Output is correct
27 Correct 4 ms 2260 KB Output is correct
28 Correct 10 ms 7252 KB Output is correct
29 Correct 9 ms 6836 KB Output is correct
30 Correct 9 ms 6868 KB Output is correct
31 Correct 9 ms 7136 KB Output is correct
32 Correct 11 ms 7252 KB Output is correct
33 Correct 1 ms 1876 KB Output is correct
34 Correct 4 ms 2272 KB Output is correct
35 Correct 79 ms 17460 KB Output is correct
36 Correct 74 ms 16876 KB Output is correct
37 Correct 81 ms 17732 KB Output is correct
38 Correct 83 ms 16848 KB Output is correct
39 Correct 75 ms 16572 KB Output is correct
40 Correct 58 ms 3104 KB Output is correct
41 Correct 67 ms 3096 KB Output is correct
42 Correct 62 ms 3120 KB Output is correct
43 Correct 63 ms 3020 KB Output is correct
44 Correct 57 ms 2936 KB Output is correct
45 Correct 48 ms 7244 KB Output is correct
46 Correct 54 ms 7248 KB Output is correct
47 Correct 49 ms 7244 KB Output is correct
48 Correct 51 ms 7160 KB Output is correct
49 Correct 50 ms 7544 KB Output is correct
50 Correct 1 ms 1876 KB Output is correct
51 Correct 48 ms 3276 KB Output is correct
52 Correct 698 ms 407224 KB Output is correct
53 Correct 671 ms 400220 KB Output is correct
54 Correct 648 ms 376284 KB Output is correct
55 Correct 624 ms 373168 KB Output is correct
56 Correct 640 ms 383404 KB Output is correct
57 Correct 74 ms 14680 KB Output is correct
58 Correct 72 ms 14672 KB Output is correct
59 Correct 73 ms 14808 KB Output is correct
60 Correct 79 ms 14668 KB Output is correct
61 Correct 83 ms 15832 KB Output is correct
62 Correct 354 ms 195024 KB Output is correct
63 Correct 384 ms 213644 KB Output is correct
64 Correct 349 ms 194924 KB Output is correct
65 Correct 357 ms 200896 KB Output is correct
66 Correct 379 ms 212696 KB Output is correct
67 Correct 1 ms 1888 KB Output is correct
68 Correct 73 ms 14936 KB Output is correct
69 Correct 815 ms 384216 KB Output is correct
70 Correct 882 ms 409088 KB Output is correct
71 Correct 798 ms 380696 KB Output is correct
72 Correct 851 ms 399088 KB Output is correct
73 Correct 838 ms 393260 KB Output is correct
74 Correct 293 ms 23228 KB Output is correct
75 Correct 264 ms 21916 KB Output is correct
76 Correct 272 ms 23368 KB Output is correct
77 Correct 254 ms 21644 KB Output is correct
78 Correct 255 ms 22140 KB Output is correct
79 Correct 453 ms 218928 KB Output is correct
80 Correct 436 ms 202556 KB Output is correct
81 Correct 423 ms 201156 KB Output is correct
82 Correct 447 ms 213084 KB Output is correct
83 Correct 414 ms 203124 KB Output is correct
84 Correct 1 ms 1876 KB Output is correct
85 Correct 132 ms 21832 KB Output is correct