oj.uz

Submission #1044669

# Submission time Handle Problem Language Result Execution time Memory
1044669 2024-08-05T12:10:34 Z beaconmc The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2789 ms 118708 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<array<ll,2>> 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)%40==0){
            lotchange[A[i]].push_back(tempedges[A[i]]);
        }
        if ((changes[B[i]].size()-1)%40==0){
            lotchange[B[i]].push_back(tempedges[B[i]]);
        }
 
 
    }
}
 
int mindiff(set<ll, cmp>&a, set<ll, cmp>&b){
 
 
    ll ans = 1000000000;
    basic_string<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(), array<ll, 2>{v, 1000000000})-changes[x].begin();
    pos--;
    
 
    set<ll, cmp> X;
    if (pos >= 0){
        X=lotchange[x][pos/40];
 
        FOR(i, (pos/40)*40+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(), array<ll, 2>{v, 1000000000})-changes[y].begin();
    pos--;
    
 
    set<ll, cmp> Y;
    if (pos >= 0){
        Y=lotchange[y][pos/40];
 
        FOR(i, (pos/40)*40+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::__cxx11::basic_string<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::__cxx11::basic_string<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 2 ms 10072 KB Output is correct
2 Correct 2 ms 10072 KB Output is correct
3 Correct 3 ms 10072 KB Output is correct
4 Correct 8 ms 10840 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 48280 KB Output is correct
2 Correct 216 ms 48208 KB Output is correct
3 Correct 228 ms 20560 KB Output is correct
4 Correct 1332 ms 84560 KB Output is correct
5 Correct 441 ms 45648 KB Output is correct
6 Correct 2369 ms 116560 KB Output is correct
7 Correct 579 ms 41264 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 48320 KB Output is correct
2 Correct 1878 ms 115024 KB Output is correct
3 Correct 1405 ms 74276 KB Output is correct
4 Correct 2611 ms 116096 KB Output is correct
5 Correct 503 ms 52704 KB Output is correct
6 Correct 2789 ms 116080 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12120 KB Output is correct
2 Correct 121 ms 10328 KB Output is correct
3 Correct 209 ms 10328 KB Output is correct
4 Correct 756 ms 12888 KB Output is correct
5 Correct 716 ms 12888 KB Output is correct
6 Correct 134 ms 11096 KB Output is correct
7 Correct 618 ms 11608 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 10072 KB Output is correct
3 Correct 2 ms 10072 KB Output is correct
4 Correct 3 ms 10072 KB Output is correct
5 Correct 8 ms 10840 KB Output is correct
6 Correct 219 ms 48280 KB Output is correct
7 Correct 216 ms 48208 KB Output is correct
8 Correct 228 ms 20560 KB Output is correct
9 Correct 1332 ms 84560 KB Output is correct
10 Correct 441 ms 45648 KB Output is correct
11 Correct 2369 ms 116560 KB Output is correct
12 Correct 579 ms 41264 KB Output is correct
13 Correct 217 ms 48320 KB Output is correct
14 Correct 1878 ms 115024 KB Output is correct
15 Correct 1405 ms 74276 KB Output is correct
16 Correct 2611 ms 116096 KB Output is correct
17 Correct 503 ms 52704 KB Output is correct
18 Correct 2789 ms 116080 KB Output is correct
19 Correct 26 ms 12120 KB Output is correct
20 Correct 121 ms 10328 KB Output is correct
21 Correct 209 ms 10328 KB Output is correct
22 Correct 756 ms 12888 KB Output is correct
23 Correct 716 ms 12888 KB Output is correct
24 Correct 134 ms 11096 KB Output is correct
25 Correct 618 ms 11608 KB Output is correct
26 Correct 778 ms 50608 KB Output is correct
27 Correct 1544 ms 74376 KB Output is correct
28 Correct 1596 ms 76408 KB Output is correct
29 Correct 1210 ms 84552 KB Output is correct
30 Correct 2576 ms 116072 KB Output is correct
31 Correct 2110 ms 118708 KB Output is correct
32 Correct 2360 ms 116340 KB Output is correct