oj.uz

Submission #1044581

# Submission time Handle Problem Language Result Execution time Memory
1044581 2024-08-05T11:10:44 Z beaconmc The Potion of Great Power (CEOI20_potion) C++14
70 / 100
 3000 ms 118688 KB 
#include <bits/stdc++.h>
 
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
 
 
 
ll h[100001];
struct cmp {
    bool operator() (ll a, ll b) const {
        if (h[a] == h[b]) return a<b;
        return h[a] < h[b];
    }
};

vector<vector<ll>> changes[100001];
vector<set<ll, cmp>> lotchange[100001];
 
void init(int N, int D, int H[]) {
    FOR(i,0,N) h[i] = H[i];
}
 
void curseChanges(int U, int A[], int B[]) {
    vector<set<ll, cmp>> tempedges;
    tempedges.resize(100001);
    FOR(i,0,U){



        if (tempedges[A[i]].find(B[i]) != tempedges[A[i]].end()){
            changes[A[i]].push_back({i, B[i]});
            tempedges[A[i]].erase(B[i]);
        }
        else{
            changes[A[i]].push_back({i, B[i]});
            tempedges[A[i]].insert(B[i]);
        }

        if (tempedges[B[i]].find(A[i]) != tempedges[B[i]].end()){
            changes[B[i]].push_back({i, A[i]});
            tempedges[B[i]].erase(A[i]);
        } 
        else{
            changes[B[i]].push_back({i, A[i]});
            tempedges[B[i]].insert(A[i]);
        }
        if ((changes[A[i]].size()-1)%50==0){
            lotchange[A[i]].push_back(tempedges[A[i]]);
        }
        if ((changes[B[i]].size()-1)%50==0){
            lotchange[B[i]].push_back(tempedges[B[i]]);
        }


    }
}
 
int mindiff(set<ll, cmp>&a, set<ll, cmp>&b){

 
    ll ans = 1000000000;
    vector<ll> A,B;
 
    for (auto&i : a) A.push_back(h[i]);
    for (auto&i : b) B.push_back(h[i]);
 

    ll l=0,r=0;
    while (l<A.size() && r<B.size()){
        ans = min(ans, abs(A[l] - B[r]));
        if (A[l] < B[r]) l++;
        else r++;
    }
    return ans;
 
    return ans;
}
 
int question(int x, int y, int v) {

    v--;
    ll ans = 1000000000;


    ll pos = upper_bound(changes[x].begin(), changes[x].end(), vector<ll>{v, 1000000000})-changes[x].begin();
    pos--;
    

    set<ll, cmp> X;
    if (pos >= 0){
        X=lotchange[x][pos/50];

        FOR(i, (pos/50)*50+1, pos+1){

            ll temp = changes[x][i][1];

            if (X.find(temp) != X.end()) X.erase(temp);
            else X.insert(temp);

        }
    }


    pos = upper_bound(changes[y].begin(), changes[y].end(), vector<ll>{v, 1000000000})-changes[y].begin();
    pos--;
    

    set<ll, cmp> Y;
    if (pos >= 0){
        Y=lotchange[y][pos/50];

        FOR(i, (pos/50)*50+1, pos+1){

            ll temp = changes[y][i][1];

            if (Y.find(temp) != Y.end()) Y.erase(temp);
            else Y.insert(temp);

        }
    }






    return mindiff(X,Y);
}

Compilation message

potion.cpp: In function 'int mindiff(std::set<int, cmp>&, std::set<int, cmp>&)':
potion.cpp:72:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while (l<A.size() && r<B.size()){
      |            ~^~~~~~~~~
potion.cpp:72:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while (l<A.size() && r<B.size()){
      |                          ~^~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:85:8: warning: unused variable 'ans' [-Wunused-variable]
   85 |     ll ans = 1000000000;
      |        ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 3 ms 10072 KB Output is correct
3 Correct 3 ms 10072 KB Output is correct
4 Correct 12 ms 11064 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 67572 KB Output is correct
2 Correct 294 ms 67656 KB Output is correct
3 Correct 299 ms 38736 KB Output is correct
4 Correct 1473 ms 92808 KB Output is correct
5 Correct 845 ms 59320 KB Output is correct
6 Correct 2562 ms 118688 KB Output is correct
7 Correct 793 ms 58960 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 67556 KB Output is correct
2 Correct 2129 ms 115604 KB Output is correct
3 Correct 1570 ms 85196 KB Output is correct
4 Correct 2705 ms 118096 KB Output is correct
5 Correct 552 ms 71084 KB Output is correct
6 Correct 2995 ms 118388 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13144 KB Output is correct
2 Correct 168 ms 11352 KB Output is correct
3 Correct 271 ms 11352 KB Output is correct
4 Correct 802 ms 13656 KB Output is correct
5 Correct 758 ms 13656 KB Output is correct
6 Correct 137 ms 12120 KB Output is correct
7 Correct 673 ms 12284 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 3 ms 10072 KB Output is correct
3 Correct 3 ms 10072 KB Output is correct
4 Correct 3 ms 10072 KB Output is correct
5 Correct 12 ms 11064 KB Output is correct
6 Correct 330 ms 67572 KB Output is correct
7 Correct 294 ms 67656 KB Output is correct
8 Correct 299 ms 38736 KB Output is correct
9 Correct 1473 ms 92808 KB Output is correct
10 Correct 845 ms 59320 KB Output is correct
11 Correct 2562 ms 118688 KB Output is correct
12 Correct 793 ms 58960 KB Output is correct
13 Correct 298 ms 67556 KB Output is correct
14 Correct 2129 ms 115604 KB Output is correct
15 Correct 1570 ms 85196 KB Output is correct
16 Correct 2705 ms 118096 KB Output is correct
17 Correct 552 ms 71084 KB Output is correct
18 Correct 2995 ms 118388 KB Output is correct
19 Correct 32 ms 13144 KB Output is correct
20 Correct 168 ms 11352 KB Output is correct
21 Correct 271 ms 11352 KB Output is correct
22 Correct 802 ms 13656 KB Output is correct
23 Correct 758 ms 13656 KB Output is correct
24 Correct 137 ms 12120 KB Output is correct
25 Correct 673 ms 12284 KB Output is correct
26 Correct 885 ms 64592 KB Output is correct
27 Correct 1507 ms 85080 KB Output is correct
28 Correct 1902 ms 88672 KB Output is correct
29 Correct 1461 ms 93008 KB Output is correct
30 Execution timed out 3084 ms 118536 KB Time limit exceeded
31 Halted 0 ms 0 KB -