oj.uz

Submission #1044667

# Submission time Handle Problem Language Result Execution time Memory
1044667 2024-08-05T12:09:22 Z beaconmc The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2622 ms 216196 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)%20==0){
            lotchange[A[i]].push_back(tempedges[A[i]]);
        }
        if ((changes[B[i]].size()-1)%20==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(), array<ll, 2>{v, 1000000000})-changes[x].begin();
    pos--;
    
 
    set<ll, cmp> X;
    if (pos >= 0){
        X=lotchange[x][pos/20];
 
        FOR(i, (pos/20)*20+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/20];
 
        FOR(i, (pos/20)*20+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 9960 KB Output is correct
3 Correct 2 ms 10072 KB Output is correct
4 Correct 13 ms 10840 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 48424 KB Output is correct
2 Correct 239 ms 48416 KB Output is correct
3 Correct 177 ms 25628 KB Output is correct
4 Correct 1238 ms 144364 KB Output is correct
5 Correct 426 ms 56492 KB Output is correct
6 Correct 2435 ms 201104 KB Output is correct
7 Correct 484 ms 50256 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 48364 KB Output is correct
2 Correct 1844 ms 208976 KB Output is correct
3 Correct 1149 ms 116556 KB Output is correct
4 Correct 2144 ms 199900 KB Output is correct
5 Correct 397 ms 57828 KB Output is correct
6 Correct 2495 ms 200528 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12120 KB Output is correct
2 Correct 113 ms 11096 KB Output is correct
3 Correct 151 ms 10580 KB Output is correct
4 Correct 620 ms 14560 KB Output is correct
5 Correct 614 ms 14168 KB Output is correct
6 Correct 114 ms 11608 KB Output is correct
7 Correct 502 ms 13144 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 3 ms 10072 KB Output is correct
3 Correct 3 ms 9960 KB Output is correct
4 Correct 2 ms 10072 KB Output is correct
5 Correct 13 ms 10840 KB Output is correct
6 Correct 233 ms 48424 KB Output is correct
7 Correct 239 ms 48416 KB Output is correct
8 Correct 177 ms 25628 KB Output is correct
9 Correct 1238 ms 144364 KB Output is correct
10 Correct 426 ms 56492 KB Output is correct
11 Correct 2435 ms 201104 KB Output is correct
12 Correct 484 ms 50256 KB Output is correct
13 Correct 206 ms 48364 KB Output is correct
14 Correct 1844 ms 208976 KB Output is correct
15 Correct 1149 ms 116556 KB Output is correct
16 Correct 2144 ms 199900 KB Output is correct
17 Correct 397 ms 57828 KB Output is correct
18 Correct 2495 ms 200528 KB Output is correct
19 Correct 29 ms 12120 KB Output is correct
20 Correct 113 ms 11096 KB Output is correct
21 Correct 151 ms 10580 KB Output is correct
22 Correct 620 ms 14560 KB Output is correct
23 Correct 614 ms 14168 KB Output is correct
24 Correct 114 ms 11608 KB Output is correct
25 Correct 502 ms 13144 KB Output is correct
26 Correct 668 ms 78988 KB Output is correct
27 Correct 1186 ms 116812 KB Output is correct
28 Correct 1323 ms 111184 KB Output is correct
29 Correct 1149 ms 144456 KB Output is correct
30 Correct 2622 ms 200332 KB Output is correct
31 Correct 2068 ms 216196 KB Output is correct
32 Correct 2421 ms 200356 KB Output is correct