oj.uz

Submission #1044672

# Submission time Handle Problem Language Result Execution time Memory
1044672 2024-08-05T12:12:08 Z beaconmc The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2645 ms 99864 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[]) {
    set<ll, cmp> tempedges[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;
    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/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(), array<ll, 2>{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::__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 3 ms 9816 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10072 KB Output is correct
2 Correct 4 ms 10072 KB Output is correct
3 Correct 4 ms 10072 KB Output is correct
4 Correct 15 ms 10904 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 48208 KB Output is correct
2 Correct 223 ms 48244 KB Output is correct
3 Correct 235 ms 19536 KB Output is correct
4 Correct 1355 ms 72288 KB Output is correct
5 Correct 507 ms 37732 KB Output is correct
6 Correct 2415 ms 99864 KB Output is correct
7 Correct 624 ms 39504 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 48396 KB Output is correct
2 Correct 1916 ms 96336 KB Output is correct
3 Correct 1389 ms 66092 KB Output is correct
4 Correct 2253 ms 99188 KB Output is correct
5 Correct 400 ms 51700 KB Output is correct
6 Correct 2541 ms 99524 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12120 KB Output is correct
2 Correct 134 ms 10328 KB Output is correct
3 Correct 232 ms 10328 KB Output is correct
4 Correct 791 ms 12632 KB Output is correct
5 Correct 733 ms 12888 KB Output is correct
6 Correct 125 ms 11096 KB Output is correct
7 Correct 629 ms 11352 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 6 ms 10072 KB Output is correct
3 Correct 4 ms 10072 KB Output is correct
4 Correct 4 ms 10072 KB Output is correct
5 Correct 15 ms 10904 KB Output is correct
6 Correct 232 ms 48208 KB Output is correct
7 Correct 223 ms 48244 KB Output is correct
8 Correct 235 ms 19536 KB Output is correct
9 Correct 1355 ms 72288 KB Output is correct
10 Correct 507 ms 37732 KB Output is correct
11 Correct 2415 ms 99864 KB Output is correct
12 Correct 624 ms 39504 KB Output is correct
13 Correct 212 ms 48396 KB Output is correct
14 Correct 1916 ms 96336 KB Output is correct
15 Correct 1389 ms 66092 KB Output is correct
16 Correct 2253 ms 99188 KB Output is correct
17 Correct 400 ms 51700 KB Output is correct
18 Correct 2541 ms 99524 KB Output is correct
19 Correct 34 ms 12120 KB Output is correct
20 Correct 134 ms 10328 KB Output is correct
21 Correct 232 ms 10328 KB Output is correct
22 Correct 791 ms 12632 KB Output is correct
23 Correct 733 ms 12888 KB Output is correct
24 Correct 125 ms 11096 KB Output is correct
25 Correct 629 ms 11352 KB Output is correct
26 Correct 737 ms 44876 KB Output is correct
27 Correct 1341 ms 65980 KB Output is correct
28 Correct 1434 ms 69548 KB Output is correct
29 Correct 1162 ms 72528 KB Output is correct
30 Correct 2645 ms 99716 KB Output is correct
31 Correct 2037 ms 99212 KB Output is correct
32 Correct 2402 ms 99680 KB Output is correct