oj.uz

Submission #291239

# Submission time Handle Problem Language Result Execution time Memory
291239 2020-09-04T23:17:32 Z model_code The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 682 ms 43896 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14592 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 12 ms 14592 KB Output is correct
4 Correct 29 ms 18808 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 32376 KB Output is correct
2 Correct 244 ms 32504 KB Output is correct
3 Correct 206 ms 30508 KB Output is correct
4 Correct 484 ms 34424 KB Output is correct
5 Correct 347 ms 28432 KB Output is correct
6 Correct 678 ms 42920 KB Output is correct
7 Correct 363 ms 33144 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 32504 KB Output is correct
2 Correct 452 ms 43512 KB Output is correct
3 Correct 406 ms 37240 KB Output is correct
4 Correct 482 ms 42872 KB Output is correct
5 Correct 255 ms 33016 KB Output is correct
6 Correct 504 ms 42872 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15740 KB Output is correct
2 Correct 90 ms 15488 KB Output is correct
3 Correct 127 ms 15480 KB Output is correct
4 Correct 303 ms 15744 KB Output is correct
5 Correct 227 ms 15736 KB Output is correct
6 Correct 94 ms 15200 KB Output is correct
7 Correct 230 ms 15744 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 10 ms 14592 KB Output is correct
4 Correct 12 ms 14592 KB Output is correct
5 Correct 29 ms 18808 KB Output is correct
6 Correct 240 ms 32376 KB Output is correct
7 Correct 244 ms 32504 KB Output is correct
8 Correct 206 ms 30508 KB Output is correct
9 Correct 484 ms 34424 KB Output is correct
10 Correct 347 ms 28432 KB Output is correct
11 Correct 678 ms 42920 KB Output is correct
12 Correct 363 ms 33144 KB Output is correct
13 Correct 227 ms 32504 KB Output is correct
14 Correct 452 ms 43512 KB Output is correct
15 Correct 406 ms 37240 KB Output is correct
16 Correct 482 ms 42872 KB Output is correct
17 Correct 255 ms 33016 KB Output is correct
18 Correct 504 ms 42872 KB Output is correct
19 Correct 49 ms 15740 KB Output is correct
20 Correct 90 ms 15488 KB Output is correct
21 Correct 127 ms 15480 KB Output is correct
22 Correct 303 ms 15744 KB Output is correct
23 Correct 227 ms 15736 KB Output is correct
24 Correct 94 ms 15200 KB Output is correct
25 Correct 230 ms 15744 KB Output is correct
26 Correct 369 ms 35104 KB Output is correct
27 Correct 484 ms 37384 KB Output is correct
28 Correct 478 ms 36984 KB Output is correct
29 Correct 469 ms 34552 KB Output is correct
30 Correct 682 ms 42896 KB Output is correct
31 Correct 633 ms 43896 KB Output is correct
32 Correct 648 ms 42872 KB Output is correct