oj.uz

Submission #964485

# Submission time Handle Problem Language Result Execution time Memory
964485 2024-04-17T01:31:19 Z pcc The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 151224 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> re;
	void getval(int now,int l,int r,int p){
		if(!now)return;
		for(int i = seg[now].head;i;i = nid[i])re.push_back(val[i]);
		if(l == r)return;
		if(mid>=p)getval(ls,l,mid,p);
		else getval(rs,mid+1,r,p);
		return;
	}
#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) {
	seg.re.clear();seg.getval(rt[x],0,mxn-1,v);
	auto ta = seg.re;
	seg.re.clear();seg.getval(rt[y],0,mxn-1,v);
	auto tb = seg.re;
	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:104:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   while(pt != tb.size()&&tb[pt]<i)pt++;
      |         ~~~^~~~~~~~~~~~
potion.cpp:105:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   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 2 ms 6488 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 12 ms 7460 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 151052 KB Output is correct
2 Correct 408 ms 151152 KB Output is correct
3 Correct 214 ms 58068 KB Output is correct
4 Correct 1813 ms 98660 KB Output is correct
5 Correct 757 ms 128136 KB Output is correct
6 Correct 2426 ms 113140 KB Output is correct
7 Correct 582 ms 124336 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 151224 KB Output is correct
2 Correct 1474 ms 77592 KB Output is correct
3 Correct 1405 ms 116296 KB Output is correct
4 Correct 2288 ms 113068 KB Output is correct
5 Correct 514 ms 148720 KB Output is correct
6 Correct 2288 ms 113028 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13564 KB Output is correct
2 Correct 61 ms 10072 KB Output is correct
3 Correct 88 ms 9544 KB Output is correct
4 Correct 607 ms 11748 KB Output is correct
5 Correct 617 ms 12672 KB Output is correct
6 Correct 91 ms 11608 KB Output is correct
7 Correct 459 ms 10512 KB Output is correct

Subtask #6
0 / 30.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 3 ms 6488 KB Output is correct
5 Correct 12 ms 7460 KB Output is correct
6 Correct 455 ms 151052 KB Output is correct
7 Correct 408 ms 151152 KB Output is correct
8 Correct 214 ms 58068 KB Output is correct
9 Correct 1813 ms 98660 KB Output is correct
10 Correct 757 ms 128136 KB Output is correct
11 Correct 2426 ms 113140 KB Output is correct
12 Correct 582 ms 124336 KB Output is correct
13 Correct 397 ms 151224 KB Output is correct
14 Correct 1474 ms 77592 KB Output is correct
15 Correct 1405 ms 116296 KB Output is correct
16 Correct 2288 ms 113068 KB Output is correct
17 Correct 514 ms 148720 KB Output is correct
18 Correct 2288 ms 113028 KB Output is correct
19 Correct 53 ms 13564 KB Output is correct
20 Correct 61 ms 10072 KB Output is correct
21 Correct 88 ms 9544 KB Output is correct
22 Correct 607 ms 11748 KB Output is correct
23 Correct 617 ms 12672 KB Output is correct
24 Correct 91 ms 11608 KB Output is correct
25 Correct 459 ms 10512 KB Output is correct
26 Correct 770 ms 67728 KB Output is correct
27 Correct 1791 ms 116452 KB Output is correct
28 Correct 1678 ms 135272 KB Output is correct
29 Correct 1910 ms 98776 KB Output is correct
30 Execution timed out 3081 ms 112984 KB Time limit exceeded
31 Halted 0 ms 0 KB -