QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#686212#5310. PaintingFreeTimeLoveWA 108ms10204kbC++143.5kb2024-10-29 08:53:282024-10-29 08:53:30

Judging History

你现在查看的是最新测评结果

  • [2024-10-29 08:53:30]
  • 评测
  • 测评结果:WA
  • 用时:108ms
  • 内存:10204kb
  • [2024-10-29 08:53:28]
  • 提交

answer

#include<bits/stdc++.h>
namespace FRTMLV{
#define ll long long 
#define LD long double
#define i7 __int128
#define re return
#define con continue
using namespace std;
template<class T>inline bool ckmin(T &a,T b){re b<a?a=b,1:0;}
template<class T>inline bool ckmax(T &a,T b){re a<b?a=b,1:0;}
const int N=6e5+5;
inline int rd(){
	int ans=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	re f?-ans:ans;
}
const int MX=1e6+1;
int n,W,tt;
int nx[N][20],siz[N];
//
set<int>st;
int hd[MX+5];
//
struct frac{
	ll x,y;
	void clr(){if(y<0)y=-y,x=-x;ll g=llabs(__gcd(x,y));x/=g,y/=g;}
	frac operator +(const frac &a)const{frac ans={x*a.y+y*a.x,y*a.y};ans.clr();re ans;}
	frac operator -(const frac &a)const{frac ans={x*a.y-y*a.x,y*a.y};ans.clr();re ans;}
	frac operator *(const frac &a)const{frac ans={x*a.x,y*a.y};ans.clr();re ans;}
	frac operator /(const frac &a)const{frac ans={x*a.y,y*a.x};ans.clr();re ans;}
	bool operator <(const frac &a)const{re x*a.y<a.x*y;}
	bool operator ==(const frac &a)const{re x*a.y==a.x*y;}
};
struct point{
	frac x,y;
	void out(){
		printf("(%lld/%lld,%lld/%lld)\n",x.x,x.y,y.x,y.y);
	}
}p[N];
struct line{
	frac k,b;
	inline frac gty(frac x){re k*x+b;}
};
inline frac gtx(line &l1,line &l2){re (l1.b-l2.b)/(l2.k-l1.k);}


int addfront(point P,int id){
	p[++tt]=P,siz[tt]=siz[id]+1,nx[tt][0]=id;
	for(int i=1;i<20;i++)nx[tt][i]=nx[nx[tt][i-1]][i-1];
	re tt;
}
int gt(int id,int sum){
	for(int i=19;i>=0;i--)
		if(sum>=(1<<i))sum-=1<<i,id=nx[id][i];
	re id;
}
void addback(int id,point P){
	p[++tt]=P,siz[id]++;
	int cnt=0;
	while(siz[id]-1>=(1<<(cnt+1)))++cnt;
//	int nid=gt(id,siz[id]-(1<<cnt));
	id=gt(id,siz[id]-(1<<cnt));
	for(int i=cnt;i;i--)nx[id][i]=tt,id=nx[id][i-1];
	nx[id][0]=tt;
}
signed main(){
	n=rd(),W=rd();
	while(n--){
		int y1=rd(),y2=rd(),fl=rd();
		frac tmp={y2-y1,W};tmp.clr();
		point P={(frac){0,1},(frac){y1,1}};
		line li={tmp,(frac){y1,1}};
		if(!tt){
			printf("(%d/1,%d/1)\n",W,y2);
			if(fl){
				p[++tt]=P;
				p[++tt]={(frac){W,1},(frac){y2,1}};
				p[++tt]={(frac){0,1},(frac){0,1}};
				nx[2][0]=1,nx[3][0]=2,nx[3][1]=1,siz[3]=3;
				hd[0]=3,st.insert(0);
				
				p[++tt]={(frac){0,1},(frac){MX,1}};
				p[++tt]={(frac){W,1},(frac){y2,1}};
				p[++tt]=P;
				nx[5][0]=4,nx[6][0]=5,nx[6][1]=4,siz[6]=3;
				hd[y1]=6,st.insert(y1);
			}
			con;
		}
		int id=hd[*(--st.lower_bound(y1))],H=id;
		int sum=siz[id]-1;
		for(int i=18;i>=0;i--){
			if(sum<(1<<i))con;
			int nwid=nx[id][i];
			if(li.gty(p[nwid].x)==p[nwid].y){
				id=nwid,sum-=1<<i;
				break;
			}
			if(p[nwid].y<li.gty(p[nwid].x))id=nwid,sum-=1<<i;
		}
		if(li.gty(p[id].x)==p[id].y){//split
			p[id].out();
			if(fl){
				siz[nx[id][0]]=sum,siz[id]-=sum;
				int num1=addfront(p[id],nx[id][0]);
				int num2=addfront(P,num1);
				st.insert(y1),hd[y1]=num2;
				
				addback(H,P);
			}
			con;
		}
		//common
		point p1=p[id],p2=p[nx[id][0]],np;
		if(p1.x==p2.x)np={(frac){W,1},(frac){y2,1}};
		else {
			frac k1=(p1.y-p2.y)/(p1.x-p2.x);
			line tmp={k1,p1.y-p1.x*k1};
			np.x=gtx(li,tmp),np.y=li.gty(np.x);
		}
		np.out();
		if(fl){
			siz[nx[id][0]]=sum,siz[id]-=sum;
			int num1=addfront(np,nx[id][0]);
			int num2=addfront(P,num1);
			st.insert(y1),hd[y1]=num2;
			
			addback(H,np);
			addback(H,P);
		}
	}
	re 0;
}
/*
4 3
1 2 1
2 1 1
3 1 0
3 2 1



*/
}signed main(){re FRTMLV::main();}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9968kb

input:

4 3
1 2 1
2 1 1
3 1 0
3 2 1

output:

(3/1,2/1)
(3/2,3/2)
(2/1,5/3)
(3/1,2/1)

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 108ms
memory: 10204kb

input:

300000 894665
1 1000000 1
2 999999 1
3 999997 1
4 999994 1
5 999990 1
6 999985 1
7 999979 1
8 999972 1
9 999964 1
10 999955 1
11 999945 1
12 999934 1
13 999922 1
14 999909 1
15 999895 1
16 999880 1
17 999864 1
18 999847 1
19 999829 1
20 999810 1
21 999790 1
22 999769 1
23 999747 1
24 999724 1
25 999...

output:

(894665/1,1000000/1)
(894665/2,1000001/2)
(894665/3,1000003/3)
(894665/4,500003/2)
(178933/1,200002/1)
(894665/6,1000015/6)
(894665/7,1000021/7)
(894665/1,999972/1)
(894665/9,1000036/9)
(178933/2,200009/2)
(894665/11,1000055/11)
(894665/12,500033/6)
(894665/13,1000078/13)
(894665/14,1000091/14)
(178...

result:

wrong answer 8th lines differ - expected: '(894665/8,250007/2)', found: '(894665/1,999972/1)'