oj.uz

Submission #888892

# Submission time Handle Problem Language Result Execution time Memory
888892 2023-12-18T10:45:21 Z Nurislam Passport (JOI23_passport) C++14
22 / 100
 53 ms 59632 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, inf = 1e18;

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 = inf;
		int x;
		cin >> x;
		set<pair<int,pii>> q;
		q.insert({1, a[x]});
		int l, r, _l, _r;
		while(!q.empty()){
			auto [cnt, tu] = *q.begin();
			q.erase(q.begin());
			l = tu.ff,r = tu.ss;
			if(l == 1 && r == n){
				ans = min(ans, cnt);
				continue;
			}
			pii fr = getmn(l, r);
			_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);
			if(sc.ss == fr.ss)continue;
			_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 == inf?-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:19:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int N = 2e5+50, inf = 1e18;
      |                             ^~~~
passport.cpp: In function 'void solve()':
passport.cpp:76:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |    auto [cnt, tu] = *q.begin();
      |         ^
passport.cpp: At global scope:
passport.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main(){
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 53 ms 59524 KB Output is correct
5 Correct 46 ms 59544 KB Output is correct
6 Correct 50 ms 59632 KB Output is correct
7 Correct 46 ms 59472 KB Output is correct
8 Correct 33 ms 59212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 3 ms 29020 KB Output is correct
12 Correct 3 ms 29020 KB Output is correct
13 Correct 3 ms 29020 KB Output is correct
14 Correct 3 ms 29020 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 3 ms 29020 KB Output is correct
12 Correct 3 ms 29020 KB Output is correct
13 Correct 3 ms 29020 KB Output is correct
14 Correct 3 ms 29020 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 4 ms 37208 KB Output is correct
17 Incorrect 6 ms 37212 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 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 3 ms 29020 KB Output is correct
12 Correct 3 ms 29020 KB Output is correct
13 Correct 3 ms 29020 KB Output is correct
14 Correct 3 ms 29020 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 4 ms 37208 KB Output is correct
17 Incorrect 6 ms 37212 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 8540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 53 ms 59524 KB Output is correct
5 Correct 46 ms 59544 KB Output is correct
6 Correct 50 ms 59632 KB Output is correct
7 Correct 46 ms 59472 KB Output is correct
8 Correct 33 ms 59212 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 3 ms 29020 KB Output is correct
20 Correct 3 ms 29020 KB Output is correct
21 Correct 3 ms 29020 KB Output is correct
22 Correct 3 ms 29020 KB Output is correct
23 Correct 4 ms 29020 KB Output is correct
24 Correct 4 ms 37208 KB Output is correct
25 Incorrect 6 ms 37212 KB Output isn't correct
26 Halted 0 ms 0 KB -