2.14 simulation summary

Preface

Happy holidays ！

( flee )
day10
50pts
expect ：10+30+20=60
actual ：0+30+20=50
rnk11

It's completely rotten .
however rnk It's not too bad , So I should not be alone …
and KH Sit side by side in the machine room , Each looking at the computer , Thinking about their own thoughts , It takes three hours to sit .
Three questions in half an hour belong to
T1 The reason for scoring is to describe the topic " attachment " It is understood as a line segment , But it's actually a straight line .
I'm not sure I'm still with KH Unified opinions
Personally, I feel that the meaning of this topic is really vague , Why not emphasize it on the home page of the competition but nail it ！ Who will watch nailing when competing qwq
The fact is that I can survive with the pruning that destroys the sky and the earth 70, I was also surprised .

title

Circle and line （circle）

A wonderful topic .
In fact, it is not as difficult as expected .
But I didn't think about it at all .
（ And the meaning of the title is confused ）

Consider two tangent points where each point falls on a circle , The corresponding two rotation angles form an interval . The necessary and sufficient condition for two points to exist simultaneously is that their corresponding intervals intersect and do not contain .
Then it becomes a line segment problem , First sort by the left endpoint , Then enumerate the first line segment violently , Put forward all the segments that legally intersect with it , Take the right endpoint and directly make a longest ascending subsequence .
（ I haven't written the longest ascending subsequence of the queue for a long time , Unexpectedly inexplicably some miss ）

Transfer stones （rock）

It is called simulating the cost flow , But personally, it's more like repentance of greed …
In fact, the general direction of my examination room is right , But this repentance is not very clear .
The key is Add a to the weight of each pair -inf, In this way, the natural guarantee will be filled .
Then try in LCA To merge , And reinsert the estoppel element .
After discussing the size relationship of several depths, we can get , After pairing, it must be bad to choose two repentance elements at the same time , So don't worry about taking the formula at the same time bug The problem of .（ Personally, I think the explanation of this place is very hasty ）

Treasure map （treasure）

Fairy scan line dp.
I haven't thought about this at all … There are only $O(k)$ individual , So I always thought it was data structure , Crazy attempt to build k Tree to tree .
The best part of this problem should be the handling of obstacles , It avoids a very troublesome up and down transfer through ingenious skills , It's really clever .
A detail is to pay attention to the obstacles, which should be added first and then deleted .

Code

T1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void write(ll x){
    
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=2e3+100;
const double pai=acos(-1.0);
const double eps=1e-10;

int n,m;
int r;
int x[N],y[N];
struct line{
    
	double x,y;
	bool operator < (const line oth)const{
    return abs(x-oth.x)>eps?x<oth.x:y<oth.y;}
}l[N];
int ans;
double a[N],q[N];
int tot,num;
int f=0;
void calc(){
    
	num=0;
	for(int i=1;i<=tot;i++){
    
		if(!num||a[i]>q[num]-eps) q[++num]=a[i];
		else{
    
			int st=1,ed=num;
			while(st<ed){
    
				int mid=(st+ed)>>1;
				if(q[mid]>a[i]-eps) ed=mid;
				else st=mid+1;
			}
			q[st]=a[i];
		}
		//printf("i=%d num=%d\n",i,num);
	}
	ans=max(ans,num);
	if(f){
    
		for(int i=1;i<=tot;i++) printf("%lf ",a[i]);
		printf("\nnum=%d\n\n",num);
	}
}

signed main(){
    
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);

	n=read();r=read();
	
	for(int i=1;i<=n;i++){
    
		x[i]=read();y[i]=read();
		double g=atan2(y[i],x[i]),d=acos(1.0*r/sqrt(x[i]*x[i]+y[i]*y[i]));
		l[i].x=g-d;l[i].y=g+d;
		if(l[i].x<-pai) l[i].x+=2*pai;
		if(l[i].y>pai) l[i].y-=2*pai;
		if(f) printf("(%lf %lf)\n",l[i].x/pai,l[i].y/pai);
		if(l[i].x>l[i].y) swap(l[i].x,l[i].y);
	}	
	if(f) puts("");
	sort(l+1,l+1+n);
	if(f) for(int i=1;i<=n;i++) printf("(%lf %lf)\n",l[i].x,l[i].y);
	for(int now=1;now<=n;now++){
    
		a[tot=1]=l[now].y;
		for(int i=now+1;i<=n&&l[i].x<l[now].y+eps;i++){
    
			if(l[i].y>l[now].y-eps) a[++tot]=l[i].y;
		}
		calc();
	}
	printf("%d\n",ans);
	return 0;
}
/* */

T2

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void write(ll x){
    
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=3e5+100;
const int M=2e6+100;
const double pai=acos(-1.0);
const ll inf=1e12;

int n,m;
int dis[M],ls[M],rs[M];
ll val[M],tot,rub[M],num;
inline int New(ll v){
    
	int now=num?rub[num--]:++tot;
	val[now]=v;
	ls[now]=rs[now]=0;dis[now]=0;
	//printf(" New: now=%d v=%lld\n",now,v);
	return now;
}
int merge(int x,int y){
    
	if(!x||!y) return x|y;
	if(val[x]>val[y]) swap(x,y);
	rs[x]=merge(rs[x],y);
	if(dis[rs[x]]>dis[ls[x]]) swap(ls[x],rs[x]);
	dis[x]=dis[rs[x]]+1;
	return x;
}
inline ll top(int &x,int op=0){
    
	if(!x) return 1e18;
	ll res=val[x];
	if(op) rub[++num]=x,x=merge(ls[x],rs[x]);
	return res;
}
struct node{
    
	int to,nxt,w;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y,int w){
    
	p[++cnt]=(node){
    y,fi[x],w};fi[x]=cnt;
}
ll dep[N];
__gnu_pbds::priority_queue<ll,greater<ll>>a[N],b[N];
int xx[N],yy[N];
ll ans,S;
void dfs(int x,int f){
    
	for(int i=fi[x];~i;i=p[i].nxt){
    
		int to=p[i].to;
		if(to==f) continue;
		dep[to]=dep[x]+p[i].w;
		dfs(to,x);
		a[x].join(a[to]);
		b[x].join(b[to]);
	}
	//printf("\ndfs: x = %d\n",x);
	int o=min(xx[x],yy[x]);xx[x]-=o;yy[x]-=o;
	S-=o;
	if(xx[x]){
    
		for(int i=1;i<=xx[x];i++){
    
			//printf(" ins A: %lld\n",dep[x]);
			a[x].push(dep[x]);
		}
	}
	else if(yy[x]){
    
		//printf(" ins B: %lld\n",dep[x]-inf);
		for(int i=1;i<=yy[x];i++){
    
			b[x].push(dep[x]-inf);
		}
	}
	//printf(" a=%d topa=%lld b=%d topb=%lld\n",a[x],top(a[x]),b[x],top(b[x]));
	while(!a[x].empty()&&!b[x].empty()){
    
		ll u=a[x].top(),v=b[x].top();
		if(u+v-2*dep[x]>=0) break;
		ans+=u+v-2*dep[x];
		a[x].pop();b[x].pop();
		a[x].push(-v+2*dep[x]);
		b[x].push(-u+2*dep[x]);
	}
	return;
}

signed main(){
    
	//freopen("rock.in","r",stdin);
	//freopen("rock.out","w",stdout);
	memset(fi,-1,sizeof(fi));cnt=-1;
	dis[0]=-1;
	n=read();
	for(int i=1;i<n;i++){
    
		int x=read(),y=read(),w=read();
		//printf("(%d %d %d)\n",x,y,w);
		addline(x,y,w);addline(y,x,w);
	}
	for(int i=1;i<=n;i++) xx[i]=read(),yy[i]=read(),S+=yy[i];
	dfs(1,0);
	printf("%lld\n",ans+S*inf);
	return 0;
}
/* */

T3

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void write(ll x){
    
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1e6;
const ll inf=1e12;

int n,m;
int o=1e6;

#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
int tr[N<<2],laz[N<<2];
inline void pushup(int k){
    
	tr[k]=tr[ls]+tr[rs];
}
inline void tag(int k){
    
	tr[k]=0;laz[k]=0;
	return;
}
inline void pushdown(int k){
    
	if(laz[k]!=-1){
    
		laz[k]=-1;
		tag(ls);tag(rs);
	}
	return;
}
int ask(int k,int l,int r,int x,int y){
    
	if(x>y) return 0;
	if(x<=l&&r<=y) return tr[k];
	pushdown(k);
	int res(0);
	if(x<=mid) res+=ask(ls,l,mid,x,y);
	if(y>mid) res+=ask(rs,mid+1,r,x,y);
	return res;
}
void add(int k,int l,int r,int p,int w){
    
	if(l==r){
    
		tr[k]+=w;return;
	}
	pushdown(k);
	if(p<=mid) add(ls,l,mid,p,w);
	else add(rs,mid+1,r,p,w);
	pushup(k);
	return;
}
void clear(int k,int l,int r,int x,int y){
    
	if(x<=l&&r<=y){
    
		tag(k);return;
	}
	pushdown(k);
	if(x<=mid) clear(ls,l,mid,x,y);
	if(y>mid) clear(rs,mid+1,r,x,y);
	pushup(k);
}

//0:block
//1:treasure
//2:query
struct ope{
    
	int op,f;
	int x,y,id;
	int l,r;
	bool operator < (const ope oth)const{
    
		if(y!=oth.y) return y>oth.y;
		else if(op!=oth.op) return op<oth.op;
		else return f>oth.f;
	}
}q[N<<1];
int tot;
int val[N],ans[N];

multiset<int>s;
multiset<int>::iterator it;

signed main(){
    
	//freopen("treasure.in","r",stdin);
	//freopen("treasure.out","w",stdout); 
	o+=2;
	memset(laz,-1,sizeof(laz));
	
	m=read();
	for(int i=1;i<=m;i++){
    
		int a=read(),b=read(),c=read(),d=read();
		++a;++b;++c;++d;
		q[++tot]=(ope){
    0,1,0,d,i,a,c};
		q[++tot]=(ope){
    0,-1,0,b-1,i,a,c};
	}
	m=read();
	for(int i=1;i<=m;i++){
    
		int x=read(),y=read();
		++x;++y;
		q[++tot]=(ope){
    1,0,x,y,0,0,0};
	}
	n=read();
	for(int i=1;i<=n;i++){
    
		int x=read(),y=read();
		++x;++y;
		q[++tot]=(ope){
    2,0,x,y,i,0,0};
	}
	sort(q+1,q+1+tot);
	
	s.insert(o);
	for(int i=1;i<=tot;i++){
    
		if(q[i].op==0){
    
			int l=q[i].l,r=q[i].r,id=q[i].id,ed=(*s.lower_bound(q[i].l));
			if(q[i].f==1){
    
				s.insert(l-1);s.insert(r);
				int res=ask(1,1,o,l,ed);
				val[id]=ask(1,1,o,r+1,ed);
				clear(1,1,o,l,r);
				add(1,1,o,l-1,res);
			}
			else{
    
				s.erase(s.find(l-1));s.erase(s.find(r));
				add(1,1,o,l-1,-val[id]);
				clear(1,1,o,l,r);
			}
		}
		else if(q[i].op==1) add(1,1,o,q[i].x,1);
		else{
    
			int pos=q[i].x;
			int ed=(*s.lower_bound(pos));
			ans[q[i].id]=ask(1,1,o,pos,ed);
		}
	}
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}
/* 1 3 */

summary

yesterday ：“ Now most of the questions can basically think of the right direction in the examination room ”
Today, I will focus on two questions directly …
《 God high The earth thick 》
There are also people in this exam AK It's something I didn't expect .
Take my knee ！

Come on tomorrow ！awa