oj.uz

Submission #1019387

# Submission time Handle Problem Language Result Execution time Memory
1019387 2024-07-10T18:42:34 Z NintsiChkhaidze The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1975 ms 23892 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define s second
#define f first 
using namespace std;

const int N = 1e5 + 5;
const int BL = 50;
 
vector <pii> v[N];
int h[N],n;
vector <vector <int>> vec[N];

void init(int N, int D, int H[]) {
	n = N;
	for (int i=1;i<=n;i++)
		h[i] = H[i - 1];
}

void curseChanges(int U, int A[], int B[]) {
	for (int i = 1; i <= U; i++){
	    int a = A[i - 1],b = B[i - 1];
	    a+=1; b+=1;
	    v[a].pb({i,b});
	    v[b].pb({i,a});
  	}
  	
  	set <int> st;
    for (int i = 1; i <= n; i++){
	    st.clear();
	    for (int j = 0; j < v[i].size(); j++){
	      int y = v[i][j].s;
	      if (st.count(y)){
	        st.erase(y);
	      }else {
	        st.insert(y);
	      }
	 
	      if (j % BL == 0){
	        vector <int> vv;
	        for (int t: st) vv.pb(t);
	        vec[i].pb(vv);
	      }
	    }
    }
}

void getneighbours(vector <int> &vv,int x,int D){
  int l = 0,r = v[x].size() - 1,res=-1;
  while (l <= r){
    int mid = (l + r) >> 1;
    if (v[x][mid].f <= D){
      res=mid;
      l=mid+1;
    }else{
      r=mid-1;
    }
  }
  if (res==-1) return;
 
  int id = res/BL;
  set <int> st;
  for (int j = id * BL + 1; j <= res; j++){
    int y = v[x][j].s;
    if (st.count(y)){
      st.erase(y);
    }else {
      st.insert(y);
    }
  }
 
  for (int k: vec[x][id]){
    if (st.count(k)){
      st.erase(k);
    }else{
      vv.pb(h[k]);
    }
  }
 
  for (int y: st)
    vv.pb(h[y]);
  sort(vv.begin(),vv.end());
}
int question(int x, int y, int days) {
	x += 1; y += 1;
  	int ans = 1e9,l1 = 0,l2 = 0;
  	
  	vector <int> nx,ny;
	getneighbours(nx,x,days);
    getneighbours(ny,y,days);
    
    while (l1 < nx.size() && l2 < ny.size()){
      ans = min(ans,abs(nx[l1] - ny[l2]));
      if (nx[l1] < ny[l2]) ++l1;
      else ++l2;
    }
    
  	return ans;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |      for (int j = 0; j < v[i].size(); j++){
      |                      ~~^~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while (l1 < nx.size() && l2 < ny.size()){
      |            ~~~^~~~~~~~~~~
potion.cpp:93:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while (l1 < nx.size() && l2 < ny.size()){
      |                              ~~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 2 ms 5464 KB Output is correct
3 Correct 3 ms 5464 KB Output is correct
4 Correct 10 ms 5972 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 19080 KB Output is correct
2 Correct 155 ms 19084 KB Output is correct
3 Correct 195 ms 11500 KB Output is correct
4 Correct 1157 ms 15440 KB Output is correct
5 Correct 540 ms 12600 KB Output is correct
6 Correct 1956 ms 23780 KB Output is correct
7 Correct 538 ms 19216 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 19184 KB Output is correct
2 Correct 937 ms 20736 KB Output is correct
3 Correct 713 ms 21048 KB Output is correct
4 Correct 974 ms 23632 KB Output is correct
5 Correct 215 ms 19600 KB Output is correct
6 Correct 1109 ms 23680 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6488 KB Output is correct
2 Correct 171 ms 5720 KB Output is correct
3 Correct 244 ms 5720 KB Output is correct
4 Correct 737 ms 6488 KB Output is correct
5 Correct 743 ms 6488 KB Output is correct
6 Correct 140 ms 5720 KB Output is correct
7 Correct 624 ms 5976 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Correct 2 ms 5464 KB Output is correct
3 Correct 2 ms 5464 KB Output is correct
4 Correct 3 ms 5464 KB Output is correct
5 Correct 10 ms 5972 KB Output is correct
6 Correct 138 ms 19080 KB Output is correct
7 Correct 155 ms 19084 KB Output is correct
8 Correct 195 ms 11500 KB Output is correct
9 Correct 1157 ms 15440 KB Output is correct
10 Correct 540 ms 12600 KB Output is correct
11 Correct 1956 ms 23780 KB Output is correct
12 Correct 538 ms 19216 KB Output is correct
13 Correct 137 ms 19184 KB Output is correct
14 Correct 937 ms 20736 KB Output is correct
15 Correct 713 ms 21048 KB Output is correct
16 Correct 974 ms 23632 KB Output is correct
17 Correct 215 ms 19600 KB Output is correct
18 Correct 1109 ms 23680 KB Output is correct
19 Correct 28 ms 6488 KB Output is correct
20 Correct 171 ms 5720 KB Output is correct
21 Correct 244 ms 5720 KB Output is correct
22 Correct 737 ms 6488 KB Output is correct
23 Correct 743 ms 6488 KB Output is correct
24 Correct 140 ms 5720 KB Output is correct
25 Correct 624 ms 5976 KB Output is correct
26 Correct 680 ms 16936 KB Output is correct
27 Correct 1089 ms 21012 KB Output is correct
28 Correct 1135 ms 21476 KB Output is correct
29 Correct 1045 ms 15288 KB Output is correct
30 Correct 1975 ms 23800 KB Output is correct
31 Correct 1795 ms 21096 KB Output is correct
32 Correct 1823 ms 23892 KB Output is correct