oj.uz

Submission #964483

# Submission time Handle Problem Language Result Execution time Memory
964483 2024-04-17T01:26:23 Z pcc The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 151116 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#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:105:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   while(pt != tb.size()&&tb[pt]<i)pt++;
      |         ~~~^~~~~~~~~~~~
potion.cpp:106:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   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 2 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 11 ms 7244 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 151116 KB Output is correct
2 Correct 444 ms 151040 KB Output is correct
3 Correct 234 ms 57964 KB Output is correct
4 Correct 2229 ms 98848 KB Output is correct
5 Correct 892 ms 128380 KB Output is correct
6 Correct 2644 ms 113116 KB Output is correct
7 Correct 705 ms 123908 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 151092 KB Output is correct
2 Correct 1396 ms 77484 KB Output is correct
3 Correct 1455 ms 116280 KB Output is correct
4 Correct 2428 ms 113356 KB Output is correct
5 Correct 502 ms 148724 KB Output is correct
6 Correct 2164 ms 112968 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13660 KB Output is correct
2 Correct 78 ms 10060 KB Output is correct
3 Correct 113 ms 9560 KB Output is correct
4 Correct 636 ms 11828 KB Output is correct
5 Correct 616 ms 12944 KB Output is correct
6 Correct 104 ms 11568 KB Output is correct
7 Correct 462 ms 10644 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 2 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 11 ms 7244 KB Output is correct
6 Correct 479 ms 151116 KB Output is correct
7 Correct 444 ms 151040 KB Output is correct
8 Correct 234 ms 57964 KB Output is correct
9 Correct 2229 ms 98848 KB Output is correct
10 Correct 892 ms 128380 KB Output is correct
11 Correct 2644 ms 113116 KB Output is correct
12 Correct 705 ms 123908 KB Output is correct
13 Correct 414 ms 151092 KB Output is correct
14 Correct 1396 ms 77484 KB Output is correct
15 Correct 1455 ms 116280 KB Output is correct
16 Correct 2428 ms 113356 KB Output is correct
17 Correct 502 ms 148724 KB Output is correct
18 Correct 2164 ms 112968 KB Output is correct
19 Correct 53 ms 13660 KB Output is correct
20 Correct 78 ms 10060 KB Output is correct
21 Correct 113 ms 9560 KB Output is correct
22 Correct 636 ms 11828 KB Output is correct
23 Correct 616 ms 12944 KB Output is correct
24 Correct 104 ms 11568 KB Output is correct
25 Correct 462 ms 10644 KB Output is correct
26 Correct 791 ms 67592 KB Output is correct
27 Correct 1793 ms 116532 KB Output is correct
28 Correct 1715 ms 135252 KB Output is correct
29 Correct 1990 ms 98776 KB Output is correct
30 Execution timed out 3099 ms 113136 KB Time limit exceeded
31 Halted 0 ms 0 KB -