oj.uz

Submission #808788

# Submission time Handle Problem Language Result Execution time Memory
808788 2023-08-05T11:03:35 Z welleyth The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 239732 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

struct node{
    node *l,*r;
    bool sum;
    node(){
        l = r = nullptr;
        sum = 0;
    }
    void recalc(){
        sum = false;
        if(l)
            sum |= l->sum;
        if(r)
            sum |= r->sum;
    }
};

inline bool Sum(node* v){
    return v ? v->sum : 0;
}

constexpr int N = (int)1e5;

vector<node*> roots[N];
vector<int> times[N];

node* upd(node* v,int l,int r,int pos){
    if(l == r){
        node* nw = new node();
        if(v)
            *nw = *v;
        nw->sum ^= 1;
        return nw;
    }
    int m = (l+r)>>1;
    node* nw = new node();
    if(v)
        *nw = *v;
    if(pos <= m){
        nw->l = upd(nw->l,l,m,pos);
        if(Sum(nw->l) == 0){
            delete nw->l;
            nw->l = nullptr;
        }
    } else {
        nw->r = upd(nw->r,m+1,r,pos);
        if(Sum(nw->r) == 0){
            delete nw->r;
            nw->r = nullptr;
        }
    }
    nw->recalc();
    return nw;
}

int H[N];
int n;
int D;

void init(int N, int D, int H[]) {
    ::D = D;
    for(int i = 0; i < N; i++){
        ::H[i] = H[i];
    }
    ::n = N;
    return;
}

void curseChanges(int U, int A[], int B[]) {
    node* root = new node();
    for(int i = 0; i < n; i++){
        roots[i].push_back(root);
        times[i].push_back(0);
    }
    for(int i = 0; i < U; i++){
        int a = A[i], b = B[i];
        int tm = i+1;
        roots[a].push_back(upd(roots[a].back(),0,n-1,b));
        times[a].push_back(tm);
        // cerr << "adding " << tm << " to " << a << " and " << b << "\n";
        roots[b].push_back(upd(roots[b].back(),0,n-1,a));
        times[b].push_back(tm);
    }
    return;
}

void get(node* v,int l,int r,vector<int>& heights){
    if(Sum(v) == 0) return;
    if(l == r){
        heights.push_back(H[l]);
        return;
    }
    int m = (l+r)>>1;
    get(v->l,l,m,heights);
    get(v->r,m+1,r,heights);
    return;
}

int question(int x, int y, int v) {
    // cerr << "x,y,v: " << x << " " << y << " " << v << "\n";
    // cerr << "times " << x << ": ";
    // for(auto& v : times[x]){
    //     cerr << v << " ";
    // }
    // cerr << "\n";
    // cerr << "times " << y << ": ";
    // for(auto& v : times[y]){
    //     cerr << v << " ";
    // }
    // cerr << "\n";
    int pos1 = upper_bound(times[x].begin(),times[x].end(),v) - times[x].begin() - 1;
    int pos2 = upper_bound(times[y].begin(),times[y].end(),v) - times[y].begin() - 1;
    // cerr << "pos1: " << pos1 << "\n";
    // cerr << "pos2: " << pos2 << "\n";
    node* root1 = roots[x][pos1];
    node* root2 = roots[y][pos2];
    vector<int> heights[2];
    get(root1,0,n-1,heights[0]);
    get(root2,0,n-1,heights[1]);
    sort(heights[0].begin(),heights[0].end());
    sort(heights[1].begin(),heights[1].end());
    int ans = (int)1e9;
    int j = 0;
    for(auto& h : heights[0]){
        while(j < heights[1].size() && heights[1][j] < h) j++;
        for(int i = max(0,j-1); i < min(j+1,(int)heights[1].size()); i++)
            ans = min(ans,abs(h-heights[1][i]));
    }
    // cerr << "ans: " << ans << "\n";
    return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         while(j < heights[1].size() && heights[1][j] < h) j++;
      |               ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5712 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 4 ms 5840 KB Output is correct
4 Correct 24 ms 13124 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 239600 KB Output is correct
2 Correct 683 ms 239616 KB Output is correct
3 Correct 369 ms 158948 KB Output is correct
4 Execution timed out 3073 ms 140776 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 239732 KB Output is correct
2 Execution timed out 3055 ms 163512 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 14928 KB Output is correct
2 Correct 126 ms 12028 KB Output is correct
3 Correct 196 ms 11712 KB Output is correct
4 Correct 1237 ms 13352 KB Output is correct
5 Correct 1148 ms 14404 KB Output is correct
6 Correct 163 ms 12240 KB Output is correct
7 Correct 923 ms 12404 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 6 ms 5712 KB Output is correct
3 Correct 4 ms 5716 KB Output is correct
4 Correct 4 ms 5840 KB Output is correct
5 Correct 24 ms 13124 KB Output is correct
6 Correct 734 ms 239600 KB Output is correct
7 Correct 683 ms 239616 KB Output is correct
8 Correct 369 ms 158948 KB Output is correct
9 Execution timed out 3073 ms 140776 KB Time limit exceeded
10 Halted 0 ms 0 KB -