oj.uz

Submission #974850

# Submission time Handle Problem Language Result Execution time Memory
974850 2024-05-04T01:52:26 Z Cookie The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 1139 ms 37240 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 19972207, pr = 31;
const int mxn = 2e5 + 5, mxq = 1e5 + 5, sq = 105, mxv = 64;
//const int base = (1 <<18);
const ll inf = 1e9, neg = -69420, inf2 = 1e14;
int n, D, u, q;
vt<int>comp[mxn + 1];
vt<vt<int>>day[mxn + 1], height[mxn + 1];
int h[mxn + 1], qa[mxn + 1], qb[mxn + 1];
void find(vt<int>&v, vt<int>&he, int x){
    int id = lower_bound(ALL(v), x) - v.begin();
    int id2 = lower_bound(ALL(he), h[x]) - he.begin();
    if(id == sz(v) || v[id] != x){
        v.insert(v.begin() + id, x);
        he.insert(he.begin() + id2, h[x]);
    }else{
        v.erase(v.begin() + id);
        he.erase(he.begin() + id2);
    }
}
int get(vt<int>&a, vt<int>&b){
    //for(auto i: a)cout << i << " ";
    //cout << "\n";
    //for(auto i: b)cout << i << " ";
    //cout << "\n";
    if(sz(a) == 0 || sz(b) == 0)return(inf);
    int r = 0, ans = inf;
    for(int i = 0; i < sz(b); i++){
        while(r < sz(a) && a[r] <= b[i]){
            ans = min(ans, b[i] - a[r++]);
        }
        if(r != sz(a))ans = min(ans, a[r] - b[i]);
    }
    return(ans);
}
void lzupd(int a){
    vt<int>nwd = day[a].back(), nwh = height[a].back();
    for(int j = sz(comp[a]) - sq; j < sz(comp[a]); j++){
        if(!j)continue;
        if(qa[comp[a][j]] == a){
        
            find(nwd, nwh, qb[comp[a][j]]);
        }else if(qb[comp[a][j]] == a){
            find(nwd, nwh, qa[comp[a][j]]);
        }
    }
    day[a].pb(nwd); height[a].pb(nwh);
}
vt<int>lzget(int x, int d){
    int block = d / sq;
    vt<int>nwd = day[x][block], nwh = height[x][block];
    for(int j = block * sq; j <= d; j++){
        if(!j)continue;
        if(qa[comp[x][j]] == x){
            find(nwd, nwh, qb[comp[x][j]]);
        }else if(qb[comp[x][j]] == x){
            find(nwd, nwh, qa[comp[x][j]]);
        }
    }
    
    return(nwh);
}
void init(int N, int _D, int H[]) {
    n = N; D = _D;
    for(int i = 0; i < n; i++)h[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < n; i++)comp[i].pb(0);
    vt<int>emp;
    for(int i = 0; i < n; i++){
        day[i].pb(emp); height[i].pb(emp);
    }
    u = U;
    for(int i = 1; i <= u; i++){
        int a, b; a = A[i - 1], b = B[i - 1];
        qa[i] = a; qb[i] = b;
        comp[a].pb(i); comp[b].pb(i);
        if(sz(comp[a]) % sq == 0){
            lzupd(a);
        }if(sz(comp[b]) % sq == 0){
            lzupd(b);
        }
    }
}

int question(int x, int y, int v) {
    int id = upper_bound(ALL(comp[x]), v) - comp[x].begin() - 1;
    int id2 = upper_bound(ALL(comp[y]), v) - comp[y].begin() - 1;
    vt<int>hx = lzget(x, id), hy = lzget(y, id2);
    return(get(hx, hy));
   
}
/*
int main() {
  int N, D, U, Q;
  std::ios::sync_with_stdio(false); std::cin.tie(NULL);
  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);

  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;
    } else {
      std::cerr << YourAnswer << " - OK" << std::endl;
    }
  }

  if (correct) {
    std::cout << "Correct." << std::endl;
  } else std::cout << "Incorrect." << std::endl;
  return 0;
}
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16472 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 5 ms 16676 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 27 ms 26764 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 30148 KB Output is correct
2 Correct 157 ms 30576 KB Output is correct
3 Correct 443 ms 30752 KB Output is correct
4 Correct 1139 ms 25072 KB Output is correct
5 Correct 508 ms 22196 KB Output is correct
6 Correct 1008 ms 35376 KB Output is correct
7 Correct 1033 ms 30712 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 30024 KB Output is correct
2 Correct 728 ms 37240 KB Output is correct
3 Correct 720 ms 33196 KB Output is correct
4 Correct 838 ms 35564 KB Output is correct
5 Correct 232 ms 30712 KB Output is correct
6 Correct 845 ms 35604 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18280 KB Output is correct
2 Correct 231 ms 18264 KB Output is correct
3 Correct 418 ms 18052 KB Output is correct
4 Correct 657 ms 18288 KB Output is correct
5 Correct 519 ms 17796 KB Output is correct
6 Correct 145 ms 17240 KB Output is correct
7 Correct 624 ms 18108 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16472 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 5 ms 16676 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 27 ms 26764 KB Output is correct
6 Correct 158 ms 30148 KB Output is correct
7 Correct 157 ms 30576 KB Output is correct
8 Correct 443 ms 30752 KB Output is correct
9 Correct 1139 ms 25072 KB Output is correct
10 Correct 508 ms 22196 KB Output is correct
11 Correct 1008 ms 35376 KB Output is correct
12 Correct 1033 ms 30712 KB Output is correct
13 Correct 147 ms 30024 KB Output is correct
14 Correct 728 ms 37240 KB Output is correct
15 Correct 720 ms 33196 KB Output is correct
16 Correct 838 ms 35564 KB Output is correct
17 Correct 232 ms 30712 KB Output is correct
18 Correct 845 ms 35604 KB Output is correct
19 Correct 46 ms 18280 KB Output is correct
20 Correct 231 ms 18264 KB Output is correct
21 Correct 418 ms 18052 KB Output is correct
22 Correct 657 ms 18288 KB Output is correct
23 Correct 519 ms 17796 KB Output is correct
24 Correct 145 ms 17240 KB Output is correct
25 Correct 624 ms 18108 KB Output is correct
26 Correct 715 ms 33160 KB Output is correct
27 Correct 891 ms 32892 KB Output is correct
28 Correct 751 ms 33056 KB Output is correct
29 Correct 975 ms 25032 KB Output is correct
30 Correct 1071 ms 35296 KB Output is correct
31 Correct 958 ms 37108 KB Output is correct
32 Correct 1020 ms 35320 KB Output is correct