oj.uz

Submission #888884

# Submission time Handle Problem Language Result Execution time Memory
888884 2023-12-18T10:33:03 Z Nurislam Passport (JOI23_passport) C++14
22 / 100
 57 ms 118612 KB 
#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 2e5+50;

int n;
pii stmn[20][N];
pii stmx[20][N];
pii getmn(int l, int r) {
    int cl = __lg(r - l + 1);
    if(min(stmn[cl][l].ff, stmn[cl][r - (1 << cl) + 1].ff) == stmn[cl][l].ff)return stmn[cl][l];
    return stmn[cl][r - (1 << cl) + 1];
}
pii getmx(int l, int r) {
    int cl = __lg(r - l + 1);
    if(max(stmx[cl][l].ff, stmx[cl][r - (1 << cl) + 1].ff) == stmx[cl][l].ff)return stmx[cl][l];
    return stmx[cl][r - (1 << cl) + 1];
}

void solve(){
	int n;
	cin >> n;
	vii a(n+1);
	for(int i = 1; i <= n; i++){
		int l, r;
		cin >> l >> r;
		a[i] = {l, r};
		stmn[0][i] = {l, i};
		stmx[0][i] = {r, i};
	}
    for (int i = 1; i <= __lg(n); i++) {
        int len = 1 << (i - 1);
        for (int j = 1; j <= n; j++) {
            stmn[i][j] = stmn[i - 1][j];
            if(stmn[i][j].ff > stmn[i-1][min(j+len, n)].ff) stmn[i][j] = stmn[i - 1][ min(j + len, n) ];
            if(stmn[i][j].ff == stmn[i-1][min(j+len, n)].ff){
				if(a[stmn[i][j].ss].ss < a[stmn[i-1][min(j+len, n)].ss].ss)stmn[i][j] = stmn[i-1][min(j+len, n)];
			}
        }
    }
    for (int i = 1; i <= __lg(n); i++) {
        int len = 1 << (i - 1);
        for (int j = 1; j <= n; j++) {
            stmx[i][j] = stmx[i - 1][j];
            if(stmx[i][j].ff < stmx[i-1][min(j+len, n)].ff) stmx[i][j] = stmx[i - 1][ min(j + len, n) ];
            if(stmx[i][j].ff == stmx[i-1][min(j+len, n)].ff){
				if(a[stmx[i][j].ss].ff > a[stmx[i-1][min(j+len, n)].ss].ff)stmx[i][j] = stmx[i-1][min(j+len, n)];
			}
        }
    }
	int q;
	cin >> q;
	while(q--){
		int ans = n+1;
		int x;
		cin >> x;
		set<pair<int,pii>> q;
		q.insert({1, a[x]});
		while(!q.empty()){
			auto [cnt, tu] = *q.begin();
			q.erase(q.begin());
			int l = tu.ff,r = tu.ss;
			if(l == 1 && r == n){
				ans = min(ans, cnt);
				while(!q.empty())q.erase(q.begin());
				break;
			}
			pii fr = getmn(l, r);
			int _l = min(l, fr.ff), _r = max(r, a[fr.ss].ss);
			if(l!=_l||r!=_r)q.insert({cnt+1, {_l, _r}});
			pii sc = getmx(l, r);
			_l = min(l, a[sc.ss].ff), _r = max(r, sc.ff);
			if(l!=_l||r!=_r)q.insert({cnt+1, {_l, _r}});
		}
		cout << (ans == n+1?-1:ans) << '\n';
	}
}
main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t = 1;
  //~ cin >> t;
  while(t--){
    solve();
  }
}

Compilation message

passport.cpp: In function 'void solve()':
passport.cpp:75:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |    auto [cnt, tu] = *q.begin();
      |         ^
passport.cpp: At global scope:
passport.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main(){
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 55 ms 118568 KB Output is correct
5 Correct 55 ms 118456 KB Output is correct
6 Correct 57 ms 118612 KB Output is correct
7 Correct 46 ms 118568 KB Output is correct
8 Correct 40 ms 117844 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 5 ms 35164 KB Output is correct
12 Correct 4 ms 35164 KB Output is correct
13 Correct 4 ms 35416 KB Output is correct
14 Correct 4 ms 35164 KB Output is correct
15 Correct 5 ms 35164 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 5 ms 35164 KB Output is correct
12 Correct 4 ms 35164 KB Output is correct
13 Correct 4 ms 35416 KB Output is correct
14 Correct 4 ms 35164 KB Output is correct
15 Correct 5 ms 35164 KB Output is correct
16 Correct 7 ms 47704 KB Output is correct
17 Incorrect 7 ms 47708 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 5 ms 35164 KB Output is correct
12 Correct 4 ms 35164 KB Output is correct
13 Correct 4 ms 35416 KB Output is correct
14 Correct 4 ms 35164 KB Output is correct
15 Correct 5 ms 35164 KB Output is correct
16 Correct 7 ms 47704 KB Output is correct
17 Incorrect 7 ms 47708 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 55 ms 118568 KB Output is correct
5 Correct 55 ms 118456 KB Output is correct
6 Correct 57 ms 118612 KB Output is correct
7 Correct 46 ms 118568 KB Output is correct
8 Correct 40 ms 117844 KB Output is correct
9 Correct 1 ms 10584 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 2 ms 14684 KB Output is correct
19 Correct 5 ms 35164 KB Output is correct
20 Correct 4 ms 35164 KB Output is correct
21 Correct 4 ms 35416 KB Output is correct
22 Correct 4 ms 35164 KB Output is correct
23 Correct 5 ms 35164 KB Output is correct
24 Correct 7 ms 47704 KB Output is correct
25 Incorrect 7 ms 47708 KB Output isn't correct
26 Halted 0 ms 0 KB -