oj.uz

Submission #964482

# Submission time Handle Problem Language Result Execution time Memory
964482 2024-04-17T01:24:54 Z pcc The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 151120 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*100],val[mxn*100];
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*50];
	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 4 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 10 ms 7764 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 151120 KB Output is correct
2 Correct 416 ms 151040 KB Output is correct
3 Correct 229 ms 58000 KB Output is correct
4 Correct 1796 ms 98904 KB Output is correct
5 Correct 888 ms 128236 KB Output is correct
6 Correct 2333 ms 113096 KB Output is correct
7 Correct 581 ms 124312 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 151084 KB Output is correct
2 Correct 1488 ms 77344 KB Output is correct
3 Correct 1388 ms 116352 KB Output is correct
4 Correct 2349 ms 112964 KB Output is correct
5 Correct 495 ms 148856 KB Output is correct
6 Correct 2305 ms 112988 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13660 KB Output is correct
2 Correct 81 ms 10072 KB Output is correct
3 Correct 102 ms 9760 KB Output is correct
4 Correct 615 ms 12092 KB Output is correct
5 Correct 626 ms 12888 KB Output is correct
6 Correct 103 ms 11608 KB Output is correct
7 Correct 473 ms 10328 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 4 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 3 ms 6488 KB Output is correct
5 Correct 10 ms 7764 KB Output is correct
6 Correct 430 ms 151120 KB Output is correct
7 Correct 416 ms 151040 KB Output is correct
8 Correct 229 ms 58000 KB Output is correct
9 Correct 1796 ms 98904 KB Output is correct
10 Correct 888 ms 128236 KB Output is correct
11 Correct 2333 ms 113096 KB Output is correct
12 Correct 581 ms 124312 KB Output is correct
13 Correct 412 ms 151084 KB Output is correct
14 Correct 1488 ms 77344 KB Output is correct
15 Correct 1388 ms 116352 KB Output is correct
16 Correct 2349 ms 112964 KB Output is correct
17 Correct 495 ms 148856 KB Output is correct
18 Correct 2305 ms 112988 KB Output is correct
19 Correct 50 ms 13660 KB Output is correct
20 Correct 81 ms 10072 KB Output is correct
21 Correct 102 ms 9760 KB Output is correct
22 Correct 615 ms 12092 KB Output is correct
23 Correct 626 ms 12888 KB Output is correct
24 Correct 103 ms 11608 KB Output is correct
25 Correct 473 ms 10328 KB Output is correct
26 Correct 783 ms 67204 KB Output is correct
27 Correct 1820 ms 116504 KB Output is correct
28 Correct 1711 ms 135396 KB Output is correct
29 Correct 1966 ms 98752 KB Output is correct
30 Execution timed out 3066 ms 112936 KB Time limit exceeded
31 Halted 0 ms 0 KB -