oj.uz

Submission #964492

# Submission time Handle Problem Language Result Execution time Memory
964492 2024-04-17T01:53:44 Z pcc The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 155328 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
#define ll long long

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;
	}
	int re[mxn],ptr = 0;
	void addv(int v){
		re[ptr++] = v;
		return;
	}
	void getval(int now,int l,int r,int p){
		if(!now)return;
		for(int i = seg[now].head;i;i = nid[i])addv(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<ll,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);
		ll h = 1ll*p.fs*mxn+p.sc;
		if(mp.find(h) != mp.end()){
			rt[p.fs] = seg.modify(rt[p.fs],0,mxn-10,mp[h]+1,i,arr[p.sc]);
			rt[p.sc] = seg.modify(rt[p.sc],0,mxn-10,mp[h]+1,i,arr[p.fs]);
			mp.erase(h);
		}
		else{
			mp[h] = i;
		}
	}
	for(auto &i:mp){
		pii p = pii(i.fs/mxn,i.fs%mxn);
		rt[p.fs] = seg.modify(rt[p.fs],0,mxn-10,i.sc+1,mxn-10,arr[p.sc]);
		rt[p.sc] = seg.modify(rt[p.sc],0,mxn-10,i.sc+1,mxn-10,arr[p.fs]);
	}
	return;
}

unordered_map<ll,int> done;

int question(int x, int y, int v) {
	if(done.find(1ll*x*mxn*mxn+1ll*y*mxn+v) != done.end())return done[1ll*x*mxn*mxn+1ll*y*mxn+v];
	seg.ptr = 0;seg.getval(rt[x],0,mxn-10,v);
	vector<int> ta;
	for(int i = 0;i<seg.ptr;i++){
		ta.push_back(seg.re[i]);
	}
	seg.ptr = 0;seg.getval(rt[y],0,mxn-10,v);
	vector<int> tb;
	for(int i = 0;i<seg.ptr;i++){
		tb.push_back(seg.re[i]);
	}
	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 done[1ll*x*mxn*mxn+1ll*y*mxn+v] = ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:120:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   while(pt != tb.size()&&tb[pt]<i)pt++;
      |         ~~~^~~~~~~~~~~~
potion.cpp:121:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   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 8536 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 155196 KB Output is correct
2 Correct 440 ms 155328 KB Output is correct
3 Correct 169 ms 58896 KB Output is correct
4 Correct 1672 ms 98772 KB Output is correct
5 Correct 796 ms 132244 KB Output is correct
6 Correct 833 ms 115252 KB Output is correct
7 Correct 606 ms 126092 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 155120 KB Output is correct
2 Correct 1563 ms 79884 KB Output is correct
3 Correct 1357 ms 118476 KB Output is correct
4 Correct 2279 ms 115236 KB Output is correct
5 Correct 509 ms 152868 KB Output is correct
6 Correct 2479 ms 115276 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15404 KB Output is correct
2 Correct 83 ms 12272 KB Output is correct
3 Correct 79 ms 11592 KB Output is correct
4 Correct 672 ms 13964 KB Output is correct
5 Correct 627 ms 14688 KB Output is correct
6 Correct 114 ms 13592 KB Output is correct
7 Correct 446 ms 12580 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 3 ms 8536 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 11 ms 9212 KB Output is correct
6 Correct 419 ms 155196 KB Output is correct
7 Correct 440 ms 155328 KB Output is correct
8 Correct 169 ms 58896 KB Output is correct
9 Correct 1672 ms 98772 KB Output is correct
10 Correct 796 ms 132244 KB Output is correct
11 Correct 833 ms 115252 KB Output is correct
12 Correct 606 ms 126092 KB Output is correct
13 Correct 425 ms 155120 KB Output is correct
14 Correct 1563 ms 79884 KB Output is correct
15 Correct 1357 ms 118476 KB Output is correct
16 Correct 2279 ms 115236 KB Output is correct
17 Correct 509 ms 152868 KB Output is correct
18 Correct 2479 ms 115276 KB Output is correct
19 Correct 66 ms 15404 KB Output is correct
20 Correct 83 ms 12272 KB Output is correct
21 Correct 79 ms 11592 KB Output is correct
22 Correct 672 ms 13964 KB Output is correct
23 Correct 627 ms 14688 KB Output is correct
24 Correct 114 ms 13592 KB Output is correct
25 Correct 446 ms 12580 KB Output is correct
26 Correct 840 ms 70180 KB Output is correct
27 Correct 1789 ms 118436 KB Output is correct
28 Correct 1733 ms 137220 KB Output is correct
29 Correct 1867 ms 98752 KB Output is correct
30 Execution timed out 3017 ms 115460 KB Time limit exceeded
31 Halted 0 ms 0 KB -