oj.uz

Submission #602193

# Submission time Handle Problem Language Result Execution time Memory
602193 2022-07-22T16:34:34 Z Theo830 The Potion of Great Power (CEOI20_potion) C++17
56 / 100
 3000 ms 77900 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
///Dremix10's template
template<typename T>
struct SPARSE{
    vector<vector<T> > sparse;
    vector<int> log;
    const int maxPow = 20;
    int N;

    void init(int n){
        sparse.assign(n,vector<T>(maxPow));
        log.assign(n+1,0);
        N = n;

        for(int i = 2;i <= n;i++)
            log[i] = log[i/2] + 1;
    }

    // supports 0-indexing
    void build(vector<T> arr){
        int i,j;
        for(i = 0;i < N ;i++)
            sparse[i][0] = arr[i];

        for(j = 1;j < maxPow;j++)
            for(i = 0;i + (1<<j) <= N;i++)
                sparse[i][j] = min(sparse[i][j-1],sparse[i+(1<<(j-1))][j-1]);
    }

    T query(int l, int r){
        int k = log[r-l+1];
        return min(sparse[l][k],sparse[r-(1<<k)+1][k]);
    }

};
vector<iii>rang[100005];
SPARSE<ll>s[100005];
ll n;
ll h[100005];
void init(int N, int D, int H[]){
    n = N;
    f(i,0,n){
        h[i] = H[i];
    }
}
void curseChanges(int U, int A[], int B[]) {
    ll u = U;
    vector<ii>exo[n];
    f(i,0,u){
        ll a = A[i],b = B[i];
        exo[a].pb(ii(b,i+1));
        exo[b].pb(ii(a,i+1));
    }
    ll last[n];
    memset(last,-1,sizeof last);
    f(i,0,n){
        set<ll>ex;
        for(auto x:exo[i]){
            if(last[x.F] == -1){
                last[x.F] = x.S;
                ex.insert(x.F);
            }
            else{
                rang[i].pb(iii(ii(x.S - 1,last[x.F]),h[x.F]));
                last[x.F] = -1;
                ex.erase(x.F);
            }
        }
        for(auto x:ex){
            rang[i].pb(iii(ii(u + 5,last[x]),h[x]));
            last[x] = -1;
        }
        sort(all(rang[i]));
        s[i].init(rang[i].size());
        vector<ll>vale;
        for(auto x:rang[i]){
            vale.pb(x.F.S);
        }
        s[i].build(vale);
    }
}
int question(int x, int y, int v) {
    ll ans = 1e9;
    vector<ii>kame;
    ll pos = lower_bound(all(rang[x]),iii(ii(v,0),0)) - rang[x].begin();
    ll L = pos;
    while(1){
        ll l = L,r = rang[x].size() - 1;
        pos = r + 1;
        while(l <= r){
            ll mid = (l+r)/2;
            if(s[x].query(L,mid) <= v){
                r = mid - 1;
                pos = min(pos,mid);
            }
            else{
                l = mid + 1;
            }
        }
        if(pos < rang[x].size()){
            kame.pb(ii(rang[x][pos].S,0));
        }
        else{
            break;
        }
        L = pos + 1;
    }
    pos = lower_bound(all(rang[y]),iii(ii(v,0),0)) - rang[y].begin();
    L = pos;
    while(1){
        ll l = L,r = rang[y].size() - 1;
        pos = r + 1;
        while(l <= r){
            ll mid = (l+r)/2;
            if(s[y].query(L,mid) <= v){
                r = mid - 1;
                pos = min(pos,mid);
            }
            else{
                l = mid + 1;
            }
        }
        if(pos < rang[y].size()){
            kame.pb(ii(rang[y][pos].S,1));
        }
        else{
            break;
        }
        L = pos + 1;
    }
    sort(all(kame));
    f(i,0,(ll)kame.size()-1){
        if(kame[i].S != kame[i+1].S){
            ans = min(ans,kame[i+1].F - kame[i].F);
        }
    }
    return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:124:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         if(pos < rang[x].size()){
      |            ~~~~^~~~~~~~~~~~~~~~
potion.cpp:147:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         if(pos < rang[y].size()){
      |            ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8144 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8528 KB Output is correct
2 Correct 6 ms 8528 KB Output is correct
3 Correct 6 ms 8528 KB Output is correct
4 Correct 38 ms 15108 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 77864 KB Output is correct
2 Correct 326 ms 77848 KB Output is correct
3 Correct 216 ms 46288 KB Output is correct
4 Correct 1830 ms 56132 KB Output is correct
5 Correct 530 ms 70956 KB Output is correct
6 Execution timed out 3078 ms 57768 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 77900 KB Output is correct
2 Correct 2993 ms 48480 KB Output is correct
3 Correct 1389 ms 58148 KB Output is correct
4 Correct 2443 ms 57928 KB Output is correct
5 Correct 480 ms 77236 KB Output is correct
6 Correct 2611 ms 57820 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11984 KB Output is correct
2 Correct 89 ms 10444 KB Output is correct
3 Correct 206 ms 10448 KB Output is correct
4 Correct 1054 ms 11344 KB Output is correct
5 Correct 1122 ms 11728 KB Output is correct
6 Correct 115 ms 11216 KB Output is correct
7 Correct 1053 ms 10576 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8144 KB Output is correct
2 Correct 8 ms 8528 KB Output is correct
3 Correct 6 ms 8528 KB Output is correct
4 Correct 6 ms 8528 KB Output is correct
5 Correct 38 ms 15108 KB Output is correct
6 Correct 327 ms 77864 KB Output is correct
7 Correct 326 ms 77848 KB Output is correct
8 Correct 216 ms 46288 KB Output is correct
9 Correct 1830 ms 56132 KB Output is correct
10 Correct 530 ms 70956 KB Output is correct
11 Execution timed out 3078 ms 57768 KB Time limit exceeded
12 Halted 0 ms 0 KB -