Submission #883923

#TimeUsernameProblemLanguageResultExecution timeMemory
883923vjudge1Passport (JOI23_passport)C++17
48 / 100
2033 ms210992 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 2e5+100, M = 1e5+10, K = 21; int n, A[N][K], B[N][K], T[4*N], ans[N]; map<int, int> dp[N]; array<int, 2> a[N]; void build(){for(int i = 0; i <= 4*n; ++i) T[i] = MOD;} void update(int l, int r, int p, int k, int val){ if(l == r){ T[k] = val; return; } int m = l+r>>1; if(p <= m) update(l, m, p, k<<1, val); else update(m+1, r, p, k<<1|1, val); T[k] = min(T[k<<1], T[k<<1|1]); } int get(int l, int r, int ql, int qr, int k){ if(ql > r || l > qr) return MOD; if(ql <= l && r <= qr) return T[k]; int m = l+r>>1; return min(get(l, m, ql, qr, k<<1), get(m+1, r, ql, qr, k<<1|1)); } int get_max(int l, int r){ int k = int(log2(r-l+1)); return max(B[l][k], B[r-(1<<k)+1][k]); } int get_min(int l, int r){ int k = int(log2(r-l+1)); return min(A[l][k], A[r-(1<<k)+1][k]); } int dfs(int l, int r){ if(dp[l].find(r) != dp[l].end()) return dp[l][r]; dp[l][r] = MOD; int val = MOD; val = min(val, get(1, n, l, r, 1)); int L = get_min(l, r); int R = get_max(l, r); if(L < l) val = min(val, dfs(L, r) + 1); if(r < R) val = min(val, dfs(l, R) + 1); // cout << l << ' ' << r << ' ' << val << '\n'; return dp[l][r] = val; } void solve(){ cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i][0] >> a[i][1]; for(int i = 1; i <= n; ++i) A[i][0] = a[i][0], B[i][0] = a[i][1]; for(int j = 1; j < K; ++j){ for(int i = 1; i + (1<<j) <= n+1; ++i){ A[i][j] = min(A[i][j - 1], A[i + (1<<(j-1))][j - 1]); B[i][j] = max(B[i][j - 1], B[i + (1<<(j-1))][j - 1]); } } vector<int> Q; for(int i = 1; i <= n; ++i) Q.pb(i); sort(all(Q), [&](const int &x, const int &y){ return (a[x][1] - a[x][0]) > (a[y][1] - a[y][0]); }); build(); dp[1][n] = 0; for(auto V: Q){ int v = V; // cout << v << ":\n"; int c = dfs(a[v][0], a[v][1]) + 1; ans[v] = c; update(1, n, v, 1, c); } int q; cin >> q; for(int i = 0; i < q; ++i){ int v; cin >> v; cout << (ans[v] >= MOD ? -1 : ans[v]) << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

passport.cpp: In function 'void update(int, int, int, int, int)':
passport.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int m = l+r>>1;
      |           ~^~
passport.cpp: In function 'int get(int, int, int, int, int)':
passport.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int m = l+r>>1;
      |           ~^~
passport.cpp: In function 'int main()':
passport.cpp:96:15: warning: unused variable 'aa' [-Wunused-variable]
   96 |   int tt = 1, aa;
      |               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...