oj.uz

Submission #370789

# Submission time Handle Problem Language Result Execution time Memory
370789 2021-02-24T16:00:28 Z Traduttore Fountain (eJOI20_fountain) C++14
100 / 100
 429 ms 78572 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define int ll
#define pll pair <ll,ll>
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define TIME 1.0*clock()/CLOCKS_PER_SEC
using namespace std;
using namespace __gnu_pbds;
mt19937_64 gen(time(0));
int n,q;
vector <int> a;
vector <int> b;
void init() {
    cin>>n>>q;
    a.resize(n + 2);
    b.resize(n + 2);
    for (int i = 0;i < n;i++)
        cin>>a[i]>>b[i];
}
ll ans = 0;
void output() {
    cout<<ans<<'\n';
}
int up[(int)(1e6) ^ 1][(int)(20)];
int sum[(int)(1e6) ^ 1][(int)(20)];
struct sparse_table {
int sp[(int)(1e6) ^ 1][(int)(20)];
inline void build() {
for (int j = 0;j < 20;j++)
{
    for (int i = 0;i + (1<<j) <= n;i++)
        if (j == 0) sp[i][j] = a[i];
    else sp[i][j] = max(sp[i][j - 1],sp[i + (1<<(j - 1))][j - 1]);
}
}
inline int get (int l,int r)
{
    int LG = __lg(r - l + 1);
    return max(sp[l][LG],sp[r - (1<<LG) + 1][LG]);
}
};
sparse_table ST;
int used[(int)(1e6) ^ 1];
vector <int> gr[(int)(1e6) ^ 1];
int pr[(int)(1e6) ^ 1];
void solve() {
    a[n] = 1e18;
    b[n] = 0;
    ++n;
    ST.build();
    for (int i = 0;i < n;i++)
    {
        for (int q = 0;q < 20;q++)
            up[i][q] = -1;
    }
    for (int i = 0;i < n;i++)
    pr[i] = i;
    for (int i = 0;i < n;i++)
    {
        int left = i;
        int right = n - 1;
        int pos = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (ST.get(i, mid) != a[i]) {
                pos = mid;
                right = mid - 1;
            }
            else left = mid + 1;
        }
        up[i][0] = pos;
    }
    for (int i = 0;i < n;i++)
    sum[i][0] = b[i];
    for (int j = 1;j <= 19;j++)
    {
        for (int i = 0;i < n;i++)
        if (j == 0) up[i][j] = pr[i],sum[i][j] = b[i];
        else  {
            up[i][j] = up[up[i][j - 1]][j - 1];
            sum[i][j] = sum[up[i][j - 1]][j - 1] + sum[i][j - 1];
        }
    }
    while (q--)
    {
        int v,k;
        cin>>v>>k;
        --v;
        ans = -1;
        int suma = 0;
        for (int q = 19;q >= 0;q--)
        {
            if (sum[v][q] >= k) continue;
            k-=sum[v][q];
            v = up[v][q];
        }
        ans = v + 1;
       if (ans >= n) ans-=n; 
       output();
    }
}
int32_t main() {
    srand(time(0));
  //freopen("input.txt","r",stdin);
 // freopen("output.txt","w",stdout);
IOS;
int test;
test = 1;
while (test--) {
    init();
    solve();
}
exit(0);}
/*2 3 3 4*/

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:96:13: warning: unused variable 'suma' [-Wunused-variable]
   96 |         int suma = 0;
      |             ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Correct 17 ms 24172 KB Output is correct
3 Correct 15 ms 24172 KB Output is correct
4 Correct 16 ms 24428 KB Output is correct
5 Correct 16 ms 24428 KB Output is correct
6 Correct 16 ms 24448 KB Output is correct
7 Correct 15 ms 24428 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 71732 KB Output is correct
2 Correct 326 ms 71020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Correct 17 ms 24172 KB Output is correct
3 Correct 15 ms 24172 KB Output is correct
4 Correct 16 ms 24428 KB Output is correct
5 Correct 16 ms 24428 KB Output is correct
6 Correct 16 ms 24448 KB Output is correct
7 Correct 15 ms 24428 KB Output is correct
8 Correct 317 ms 71732 KB Output is correct
9 Correct 326 ms 71020 KB Output is correct
10 Correct 16 ms 24360 KB Output is correct
11 Correct 163 ms 53484 KB Output is correct
12 Correct 429 ms 78572 KB Output is correct
13 Correct 355 ms 78060 KB Output is correct
14 Correct 264 ms 77292 KB Output is correct
15 Correct 230 ms 77676 KB Output is correct