oj.uz

Submission #964477

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

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

const int mxn = 2e5+10;

int nid[mxn*50],val[mxn*50];
int vcnt = 0;

struct node{
	int head;
	int pl,pr;
};

int add(int now,int v){
	vcnt++;
	nid[vcnt] = now;
	val[vcnt] = v;
	return vcnt;
}

struct SEG{
#define mid ((l+r)>>1)
#define ls seg[now].pl
#define rs seg[now].pr
	node seg[mxn*20];
	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].head = add(seg[now].head,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>();
		vector<int> re;
		if(l == r){
			for(int i = seg[now].head;i;i = nid[i])re.push_back(val[i]);
			return re;
		}
		if(mid>=p)re = getval(ls,l,mid,p);
		else re = getval(rs,mid+1,r,p);
		for(int i = seg[now].head;i;i = nid[i])re.push_back(val[i]);
		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:103:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   while(pt != tb.size()&&tb[pt]<i)pt++;
      |         ~~~^~~~~~~~~~~~
potion.cpp:104:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   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 1 ms 6488 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 6488 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 11 ms 7704 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 95132 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 95124 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16044 KB Output is correct
2 Correct 79 ms 7992 KB Output is correct
3 Correct 104 ms 7580 KB Output is correct
4 Correct 641 ms 10072 KB Output is correct
5 Correct 627 ms 12896 KB Output is correct
6 Correct 108 ms 11608 KB Output is correct
7 Correct 448 ms 8252 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 3 ms 6488 KB Output is correct
5 Correct 11 ms 7704 KB Output is correct
6 Incorrect 294 ms 95132 KB Incorrect
7 Halted 0 ms 0 KB -