oj.uz

Submission #758788

# Submission time Handle Problem Language Result Execution time Memory
758788 2023-06-15T10:05:03 Z gagik_2007 The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2464 ms 223504 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

#pragma GCC optimize("O2")

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 7;
int n;
int a[MAXN];
vector<pair<int, int>>q[MAXN];
vector<int>vi[MAXN];
vector<multiset<int>>v[MAXN];
set<int>curv[MAXN];
int T;

void init(int N, int D, int H[]) {
    n = N;
    multiset<int>empty;
    empty.clear();
    for (int i = 0; i < n; i++) {
        a[i] = H[i];
        v[i].push_back(empty);
        vi[i].push_back(-1);
    }
    T = 20;
}

multiset<int>to_multiset(const set<int>&s){
    multiset<int>res;
    for(int x:s){
        res.insert(a[x]);
    }
    return res;
}

void curseChanges(int U, int A[], int B[]) {
    for(int i=0;i<U;i++){
        if(curv[A[i]].find(B[i])!=curv[A[i]].end()){
            // A[i]
            q[A[i]].push_back({i, -(B[i]+1)});
            curv[A[i]].erase(curv[A[i]].find(B[i]));

            // B[i]
            q[B[i]].push_back({i, -(A[i]+1)});
            curv[B[i]].erase(curv[B[i]].find(A[i]));
        }
        else{
            // A[i]
            q[A[i]].push_back({i, (B[i]+1)});
            curv[A[i]].insert(B[i]);

            // B[i]
            q[B[i]].push_back({i, (A[i]+1)});
            curv[B[i]].insert(A[i]);
        }

        if(q[A[i]].size()%T==0){
            v[A[i]].push_back(to_multiset(curv[A[i]]));
            vi[A[i]].push_back(i);
        }

        if(q[B[i]].size()%T==0){
            v[B[i]].push_back(to_multiset(curv[B[i]]));
            vi[B[i]].push_back(i);
        }
    }
}

double c_ery = 0, v_ery = 0;
double vva = 0;
vector<int>ex,ey;
vector<int>ax,ay;

int question(int x, int y, int u) {
    ex.clear(), ey.clear(), ax.clear(), ay.clear();
    // x
    auto it=lower_bound(vi[x].begin(),vi[x].end(),u);
    it--;
    int ind=it-vi[x].begin(); // v[x][ind]
    int day=*it;
    
    auto it2=upper_bound(q[x].begin(),q[x].end(),make_pair(day, int(1e9)));
    while(it2!=q[x].end()&&(*it2).ff<u){
        if((*it2).ss>0){
            ax.push_back(a[(*it2).ss-1]);
            v[x][ind].insert(a[(*it2).ss-1]);
        }
        else{
            ex.push_back(a[-(*it2).ss-1]);
            v[x][ind].erase(v[x][ind].find(a[-(*it2).ss-1]));
        }
        it2++;
    }
    
    // y
    it=lower_bound(vi[y].begin(),vi[y].end(),u);
    it--;
    int ind2=it-vi[y].begin();
    day=*it;
    it2=upper_bound(q[y].begin(),q[y].end(),make_pair(day, int(1e9)));
    while(it2!=q[y].end()&&(*it2).ff<u){
        if((*it2).ss>0){
            ay.push_back(a[(*it2).ss-1]);
            v[y][ind2].insert(a[(*it2).ss-1]);
        }
        else{
            ey.push_back(a[-(*it2).ss-1]);
            v[y][ind2].erase(v[y][ind2].find(a[-(*it2).ss-1]));
        }
        it2++;
    }
    // finding the closest
    int ans = 1e9;
    auto ix = v[x][ind].begin();
    auto iy = v[y][ind2].begin();
    while(ix!=v[x][ind].end()&&iy!=v[y][ind2].end()){
        ans=min(ans,abs(*ix-*iy));
        if(*ix<=*iy)ix++;
        else iy++;
    }

    // het lcenq
    for(int i:ex){
        v[x][ind].insert(i);
    }
    for(int i:ax){
        v[x][ind].erase(v[x][ind].find(i));
    }

    for(int i:ey){
        v[y][ind2].insert(i);
    }
    for(int i:ay){
        v[y][ind2].erase(v[y][ind2].find(i));
    }

    // cout<<"OK"<<endl;

    return ans;
}

// int main() {
//     int N, D, U, Q;
//     std::ios::sync_with_stdio(false); std::cin.tie(NULL);
//     freopen("input10.txt","r", stdin);
//     std::cin >> N >> D >> U >> Q;

//     int *F = new int[N];
//     for (int i=0; i<N; i++)
//         std::cin >> F[i];
//     init(N, D, F);

//     int *A = new int[U], *B = new int[U];
//     for (int i=0; i<U; i++) {
//         std::cin >> A[i] >> B[i];
//     }
//     curseChanges(U, A, B);
//     clock_t fileend = clock();
//     double filetime = double(fileend - start) / double(CLOCKS_PER_SEC);
//     cout<<"File opening: "<<filetime<<" secs."<<endl;

//     clock_t qstart = clock();
//     bool correct = true;
//     for (int i=0; i<Q; i++) {
//         int X,Y,V,CorrectAnswer;
//         std::cin >> X >> Y >> V >> CorrectAnswer;
//         int YourAnswer = question(X,Y,V);
//         if (YourAnswer != CorrectAnswer) {
//             std::cout << "WA! Question: " << i
//                 << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
//                     <<  "Your answer: " << YourAnswer
//                         << " Correct Answer: " << CorrectAnswer << std::endl;
//             correct = false;
//             return 0;
//         } else {
//             // std::cerr << YourAnswer << " - OK" << std::endl;
//         }
//     }
//     clock_t qend = clock();
//     double time_taken
//         = double(qend - qstart)
//           / double(CLOCKS_PER_SEC);
//     cout<<"Questions execution time: "<<time_taken<<" secs."<<endl;
//     cout<<"From which:\nC-ery: "<<c_ery<<" secs.\nV-ery: "<<v_ery<<" secs."<<endl;
//     cout<<"vva: "<<vva<<" secs."<<endl;

//     if (correct) {
//         std::cout << "Correct." << std::endl;
//     } else std::cout << "Incorrect." << std::endl;
//     end = clock();
//     time_taken
//         = double(end - start)
//           / double(CLOCKS_PER_SEC);
 
//     // Print the Calculated execution time
//     cout << "Execution time: " << time_taken
//          << " secs.";
//     return 0;
// }

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12240 KB Output is correct
2 Correct 7 ms 12240 KB Output is correct
3 Correct 8 ms 12240 KB Output is correct
4 Correct 26 ms 22304 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 49208 KB Output is correct
2 Correct 314 ms 49220 KB Output is correct
3 Correct 232 ms 37252 KB Output is correct
4 Correct 1234 ms 146712 KB Output is correct
5 Correct 549 ms 58984 KB Output is correct
6 Correct 1727 ms 202868 KB Output is correct
7 Correct 509 ms 52436 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 49268 KB Output is correct
2 Correct 1658 ms 216364 KB Output is correct
3 Correct 1207 ms 118848 KB Output is correct
4 Correct 1983 ms 202144 KB Output is correct
5 Correct 385 ms 58768 KB Output is correct
6 Correct 2068 ms 202596 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14416 KB Output is correct
2 Correct 127 ms 13908 KB Output is correct
3 Correct 159 ms 13896 KB Output is correct
4 Correct 344 ms 17012 KB Output is correct
5 Correct 294 ms 16568 KB Output is correct
6 Correct 135 ms 13936 KB Output is correct
7 Correct 307 ms 16080 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 7 ms 12240 KB Output is correct
3 Correct 7 ms 12240 KB Output is correct
4 Correct 8 ms 12240 KB Output is correct
5 Correct 26 ms 22304 KB Output is correct
6 Correct 304 ms 49208 KB Output is correct
7 Correct 314 ms 49220 KB Output is correct
8 Correct 232 ms 37252 KB Output is correct
9 Correct 1234 ms 146712 KB Output is correct
10 Correct 549 ms 58984 KB Output is correct
11 Correct 1727 ms 202868 KB Output is correct
12 Correct 509 ms 52436 KB Output is correct
13 Correct 276 ms 49268 KB Output is correct
14 Correct 1658 ms 216364 KB Output is correct
15 Correct 1207 ms 118848 KB Output is correct
16 Correct 1983 ms 202144 KB Output is correct
17 Correct 385 ms 58768 KB Output is correct
18 Correct 2068 ms 202596 KB Output is correct
19 Correct 42 ms 14416 KB Output is correct
20 Correct 127 ms 13908 KB Output is correct
21 Correct 159 ms 13896 KB Output is correct
22 Correct 344 ms 17012 KB Output is correct
23 Correct 294 ms 16568 KB Output is correct
24 Correct 135 ms 13936 KB Output is correct
25 Correct 307 ms 16080 KB Output is correct
26 Correct 741 ms 85684 KB Output is correct
27 Correct 1212 ms 118880 KB Output is correct
28 Correct 1230 ms 112452 KB Output is correct
29 Correct 1400 ms 146972 KB Output is correct
30 Correct 2464 ms 202320 KB Output is correct
31 Correct 2348 ms 223504 KB Output is correct
32 Correct 2370 ms 202584 KB Output is correct