oj.uz

Submission #964474

# Submission time Handle Problem Language Result Execution time Memory
964474 2024-04-17T01:16:50 Z pcc The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 564 ms 254524 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e5+10;

struct node{
	vector<int> v;
	int pl,pr;
};

struct SEG{
#define mid ((l+r)>>1)
#define ls seg[now].pl
#define rs seg[now].pr
	node seg[mxn*60];
	int ppp = 0;
	SEG(){}
	int newnode(){
		return ++ppp;
	}
	int modify(int now,int l,int r,int s,int e,int v){
		if(!now)now = newnode();
		if(l>=s&&e>=r){
			seg[now].v.push_back(v);
			return now;
		}
		if(mid>=s)ls = modify(ls,l,mid,s,e,v);
		if(mid<e)rs = modify(rs,mid+1,r,s,e,v);
		return now;
	}
	vector<int> getval(int now,int l,int r,int p){
		if(!now)return vector<int>();
		if(l == r)return seg[now].v;
		vector<int> re;
		if(mid>=p)re = getval(ls,l,mid,p);
		else re = getval(rs,mid+1,r,p);
		for(auto &j:seg[now].v)re.push_back(j);
		return re;
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
int arr[mxn],N,D;
int rt[mxn];

void init(int NN, int DD, int H[]) {
	N = NN,D = DD;
	for(int i = 0;i<N;i++){
		arr[i] = H[i];
	}
	return;
}

void curseChanges(int U, int A[], int B[]) {
	map<pii,int> mp;
	for(int i = 0;i<U;i++){
		pii p = {A[i],B[i]};
		if(p.fs>p.sc)swap(p.fs,p.sc);
		if(mp.find(p) != mp.end()){
			rt[p.fs] = seg.modify(rt[p.fs],0,mxn-1,mp[p]+1,i,arr[p.sc]);
			rt[p.sc] = seg.modify(rt[p.sc],0,mxn-1,mp[p]+1,i,arr[p.fs]);
			mp.erase(p);
		}
		else{
			mp[p] = i;
		}
	}
	for(auto &i:mp){
		rt[i.fs.fs] = seg.modify(rt[i.fs.fs],0,mxn-1,i.sc+1,mxn-1,arr[i.fs.sc]);
		rt[i.fs.sc] = seg.modify(rt[i.fs.sc],0,mxn-1,i.sc+1,mxn-1,arr[i.fs.fs]);
	}
	return;
}

int question(int x, int y, int v) {
	auto ta = seg.getval(rt[x],0,mxn-1,v);
	auto tb = seg.getval(rt[y],0,mxn-1,v);
	sort(ta.begin(),ta.end());
	sort(tb.begin(),tb.end());
	int pt = 0;
	int ans = 1e9;
	for(auto &i:ta){
		while(pt != tb.size()&&tb[pt]<i)pt++;
		if(pt != tb.size())ans = min(ans,abs(i-tb[pt]));
		if(pt-1>=0)ans = min(ans,abs(i-tb[pt-1]));
	}
	return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:90:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   while(pt != tb.size()&&tb[pt]<i)pt++;
      |         ~~~^~~~~~~~~~~~
potion.cpp:91:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   if(pt != tb.size())ans = min(ans,abs(i-tb[pt]));
      |      ~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 188964 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 189416 KB Output is correct
2 Correct 42 ms 189520 KB Output is correct
3 Correct 43 ms 189496 KB Output is correct
4 Correct 53 ms 191224 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 409 ms 254524 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 392 ms 254524 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 194808 KB Output is correct
2 Correct 126 ms 191328 KB Output is correct
3 Correct 150 ms 190764 KB Output is correct
4 Correct 548 ms 193104 KB Output is correct
5 Correct 564 ms 193908 KB Output is correct
6 Correct 148 ms 193348 KB Output is correct
7 Correct 448 ms 191544 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 188964 KB Output is correct
2 Correct 43 ms 189416 KB Output is correct
3 Correct 42 ms 189520 KB Output is correct
4 Correct 43 ms 189496 KB Output is correct
5 Correct 53 ms 191224 KB Output is correct
6 Incorrect 409 ms 254524 KB Incorrect
7 Halted 0 ms 0 KB -