Submission #849244

#	Time	Username	Problem	Language	Result	Execution time	Memory
849244		faruk	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	449 ms	44116 KiB

potion

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

/*
Save neighbour list by node, reduce storage space by constant factor (DIF)

Made for your by Mate Busa
*/

const int INF = 1000000000;
const int DIF = 50; //other numbers would also work, but i like this number
int NN, cur, goes, last, place, vv, a, b, ans;
int HH[100000];
int who[2][DIF];
int step[2];
int id[2];
int num[2];
int st[2];
int p[2][100000];
bool in[100000];
bool out[2][100000];
struct point{
    int a, day, id;
    bool in;
};
vector<pair<int,int> > change[100000];
vector<point> update[100000];
vector<pair<int,int> > vec[400000];
set<pair<int,int> > szet;
int news[2][DIF];

void init(int N, int D, int H[]) {
    NN = N; cur = 1;
    for(int i=0; i<N; i++) HH[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
    for(int i=0; i<U; i++) {
        change[A[i]].push_back({B[i],i+1});
        change[B[i]].push_back({A[i],i+1});
    }
    for(int i=0; i<NN; i++){
        update[i].resize(change[i].size()+1); update[i][0].day = 0; update[i][0].id = 0; goes = 1;
        szet.clear();
        for(pair<int,int> j:change[i]){
            in[j.first] = !in[j.first];
            update[i][goes].in = in[j.first];
            update[i][goes].a = j.first;
            update[i][goes].day = j.second;
            if(in[j.first]){
                szet.insert({HH[j.first],j.first});
            } else {
                szet.erase({HH[j.first],j.first});
            }
            if(goes%DIF==0){
                vec[cur].resize(szet.size()); place = 0;
                for(pair<int,int> k:szet) vec[cur][place++] = k;
                update[i][goes].id = cur++;
            } else {
                update[i][goes].id = -1;
            }
            goes++;
        }
        for(pair<int,int> j:szet) in[j.second] = false;
    }
}

int bi(int x, int y){
    if(x==y) return x;
    int fel = (x+y+1)/2;
    if(update[place][fel].day<=vv) return bi(fel,y);
    return bi(x,fel-1);
}
void choose(int x, int y){
    place = x; place = bi(0,update[x].size()-1);
    step[y] = 0; num[y] = 0;
    while(update[x][place].id==-1){
        a = update[x][place].a;
        if(!in[a]){
            in[a] = true;
            if(update[x][place].in){
                news[y][num[y]++] = HH[a];
            } else {
                out[y][a] = true;
            }
        }
        who[y][step[y]++] = a;
        place--;
    }
    sort(news[y],news[y]+num[y]);
    for(int i=0; i<step[y]; i++) {in[who[y][i]] = false;}
    id[y] = update[x][place].id;
}
int question(int x, int y, int v) {
    vv = v;
    choose(x,0); choose(y,1);
    ans = INF;
    for(int i=0; i<2; i++){
        int aa = 0, bb = 0; st[i] = 0;
        while(aa<vec[id[i]].size() || bb<num[i]){
            if(aa==vec[id[i]].size()){
                p[i][st[i]++] = news[i][bb++];
            } else if(bb==num[i]){
                if(!out[i][vec[id[i]][aa].second]) p[i][st[i]++] = vec[id[i]][aa].first;
                aa++;
            } else if(vec[id[i]][aa].first<news[i][bb]){
                if(!out[i][vec[id[i]][aa].second]) p[i][st[i]++] = vec[id[i]][aa].first;
                aa++;
            } else {
                p[i][st[i]++] = news[i][bb++];
            }
        }
    }
    int g = 0;
    for(int i=0; i<st[0]; i++){
        while(g<st[1] && p[1][g]<p[0][i]){
            ans = min(ans,p[0][i] - p[1][g++]);
        }
        if(g==st[1]) break;
        ans = min(ans,p[1][g] - p[0][i]);
    }


    for(int i=0; i<2; i++){
        for(int j=0; j<step[i]; j++) out[i][who[i][j]] = false;
    }
    return ans;
}

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while(aa<vec[id[i]].size() || bb<num[i]){
      |               ~~^~~~~~~~~~~~~~~~~~
potion.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             if(aa==vec[id[i]].size()){
      |                ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30