oj.uz

Submission #910125

# Submission time Handle Problem Language Result Execution time Memory
910125 2024-01-17T23:31:03 Z Alphanumeric Fountain (eJOI20_fountain) C++14
100 / 100
 321 ms 37780 KB 
/*
⣿⣿⡿⣫⣾⠏⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣀⣀⣀⣀⠄⠄⠄⠄⠄⠄
⣿⡇⠱⠉⠁⠄⠄⠄⠄⠄⠄⢀⣀⣤⣶⣶⣿⣿⣿⣿⣿⣿⣿⣦⠄⠄⠄⠄⠄
⣿⡇⠄⠄⠄⠄⠄⢀⣠⣛⡩⣩⣭⡹⣿⣿⣿⣿⠞⣛⣛⣛⡲⣿⡇⠄⠄⠄⠄
⣿⡇⠄⠄⠄⡾⣡⣾⣿⣷⣹⣿⣿⡿⣪⡻⠟⣱⣿⣿⣿⣿⣿⣷⡹⠄⠄⠄⠄
⣿⡇⠄⠄⣼⡇⣿⣻⣿⠟⡛⢿⣿⣾⣿⡇⢰⣍⢻⡿⠛⢿⣿⡭⣿⣷⠄⠄⠄
⣿⣧⣄⡀⣿⡇⣮⣽⣿⣮⣉⣾⣿⣿⣿⣇⡸⣿⣿⣆⠛⣰⣿⣾⡿⣿⠄⠄⠄
⣿⣇⡼⣄⣿⣿⡄⠙⢿⣏⣿⣿⡮⠁⣉⣾⣷⡈⠃⢿⣿⣬⡭⠝⣀⣿⠄⠄⠐
⡆⡇⣹⣿⣿⣿⣿⡿⠓⠛⣉⣉⣉⣉⣙⣛⠓⠾⣟⢿⣿⣿⣿⣿⣿⣿⣿⠇⠄⠙
⠁⡇⣞⣿⡿⠋⠁⠄⠄⠈⠉⠙⠛⠛⠻⠿⠿⠿⣶⣌⠻⣿⣿⣿⣿⣿⢗⢴⣆⢣
⠸⣇⡻⠈⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⢻⣷⡌⢿⣿⣿⣿⢸⠼⣣⣾
⣦⡀⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⠄⠄⠄⠄⠄⠄⠄⠄⠙⠛⠈⣿⡫⡼⢠⣾⣿⣿
⣿⣇⠄⣀⣠⡀⠄⠄⠴⠾⠿⠿⠶⠶⣦⣤⡀⠄⠄⠄⠄⠄⠄⢨⠯⢁⣿⣿⣿⣿
⣿⣿⣦⢒⠤⣅⡶⣶⣶⣾⣿⣿⣿⣷⣶⣮⣍⠢⠄⠄⠄⠄⠄⠐⢠⣾⣿⣿⣿⣿
⣿⣿⣿⣧⡐⠫⣉⡿⣬⡞⢿⣿⢯⠽⣶⡽⢟⣛⢖⣨⣛⠛⢃⣴⣿⣿⣿⣿⣿⣿
*/

// beichen is a classic problem in china
// map<pair<int,pair<int,int>>,priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>>> m;
// ^^ useless ds for good luck

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzworks,popworks")

using namespace std;
#define int long long

#define inp(arr) \
  for (auto &it : arr) cin >> it;
#define outp(arr) \
  for (auto it : arr) cout << it << " ";
#define inppair(arr) \
  for (pair<int, int> & it : arr) cin >> it.first >> it.second;
#define outppair(arr) \
  for (pair<int, int> it : arr) cout << it.first << " " << it.second << "\n";
#define for0(n) for (int i = 0; i < n; ++i)
#define for0j(n) for (int j = 0; j < n; ++j)
#define for0k(n) for (int k = 0; k < n; ++k)
#define for1(n) for (int i = 1; i <= n; ++i)
#define for1j(n) for (int j = 1; j <= n; ++j)
#define for1k(n) for (int k = 1; k <= n; ++k)
#define for1b(n) for (int i = n; i > 0; --i)
#define for1bj(n) for (int j = n; j > 0; --j)
#define for0b(n) for (int i = n - 1; i >= 0; --i)
#define for0bj(n) for (int j = n - 1; j >= 0; --j)
#define forself(start, end) for (int i = start; i < end; ++i)
#define vecall(v) v.begin(), v.end()
#define srt(arr) sort(arr, arr + (sizeof(arr) / sizeof(arr[0])))
#define srtvc(arr) sort(arr.begin(), arr.end())
#define bcsrt(arr) sort(arr, arr + (sizeof(arr) / sizeof(arr[0])), greater<int>())
#define bcsrtvc(arr) sort(arr.begin(), arr.end(), greater<int>())
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define pq priority_queue
#define pii pair<int, int>
#define bkpqi priority_queue<int, vector<int>, greater<int>>
#define bkpqpii priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
#define setzero(arr) memset(arr, 0, sizeof(arr));
#define setone(arr) memset(arr, 1, sizeof(arr));
#define setneg(arr) memset(arr, -1, sizeof(arr));
#define mod1 998244353
#define mod2 1000000007

using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

int n, q;
int mem[100005][20];
int pre[100005][20];

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  int a, b;
  stack<pii> st;
  for0(n) {
    cin >> a >> b;
    pre[i+1][0] = b;
    while (st.size() && st.top().first < a) {
      mem[st.top().second][0] = i + 1;
      st.pop();
    }
    st.push({a, i + 1});
  }
  while (st.size()) {
    mem[st.top().second][0] = 0;
    st.pop();
  }
  mem[0][0] = 0;
  pre[0][0] = 0;
  for1j(19) {
    for0(n + 1) {
      mem[i][j] = mem[mem[i][j - 1]][j - 1];
      pre[i][j] = pre[i][j - 1] + pre[mem[i][j - 1]][j - 1];
    }
  }
  while(q--){
    cin>>a>>b;
    for0b(20){
      if(pre[a][i]<b){
        b-=pre[a][i];
        a=mem[a][i];
      }
    }
    cout<<a<<"\n";
  }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2524 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 34828 KB Output is correct
2 Correct 237 ms 35404 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2524 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 260 ms 34828 KB Output is correct
9 Correct 237 ms 35404 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 57 ms 23380 KB Output is correct
12 Correct 321 ms 36640 KB Output is correct
13 Correct 142 ms 36580 KB Output is correct
14 Correct 118 ms 35848 KB Output is correct
15 Correct 100 ms 37780 KB Output is correct