QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88993#4906. 球球zhouhuanyi0 8ms3768kbC++233.3kb2023-03-18 09:36:592023-03-18 09:37:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-18 09:37:01]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:3768kb
  • [2023-03-18 09:36:59]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#define N 1000000
#define inf 1e18
#define INF 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0,f=1;
    while (c!='-'&&(c<'0'||c>'9')) c=getchar();
    if (c=='-') c=getchar(),f=-1;
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum*f;
}
void Adder(long long &x,long long d)
{
    x=(x<d)?x:d;
    return;
}
struct reads
{
    long long t,x;
};
reads st[N+1];
struct node
{
    int l,r,d;
    bool operator < (const node &t)const
    {
	return r<t.r;
    }
};
int n,L[N+1],lst[N+1],nt[N+1];
long long dp[N+1][2];
set<node>s;
map<int,int>p;
void adder(int l,int r,int d)
{
    int L,R,ds;
    for (auto it=s.lower_bound((node){0,l,0});(*it).l<=r&&it!=s.end();it=s.lower_bound((node){0,l,0}))
    {
	L=(*it).l,R=(*it).r,ds=(*it).d,s.erase(it);
	if (L<=l-1) s.insert((node){L,l-1,ds});
	if (r+1<=R) s.insert((node){r+1,R,ds});
    }
    s.insert((node){l,r,d});
    return;
}
int query(int x)
{
    auto it=s.lower_bound((node){0,x,0});
    return (*it).d;
}
int main()
{
    long long d,l,r,sl,sr,ps,ps2;
    n=read(),s.insert((node){(int)(-INF),(int)(INF),0});
    for (int i=1;i<=n;++i) st[i].t=read(),st[i].x=read(),L[i]=1;
    for (int i=0;i<=n;++i) dp[i][0]=dp[i][1]=inf;
    for (int i=1;i<=n;++i)
    {
	if (st[i].x==st[i-1].x) lst[i]=lst[i-1];
	else lst[i]=i-1;
    }
    nt[n+1]=n+1;
    for (int i=n;i>=1;--i)
    {
	if (st[i+1].x==st[i].x) nt[i]=nt[i+1];
	else nt[i]=i+1;
    }
    for (int i=2;i<=n;++i)
    {
	L[i]=max(max(L[i],query(st[i].x)),p[st[i].x]);
	if (lst[i-1]&&st[i-1].x!=st[i].x&&st[lst[i-1]].x!=st[i-1].x&&abs(st[i].x-st[lst[i-1]].x)>st[i].t-st[lst[i-1]].t) p[st[i].x]=max(p[st[i].x],lst[i-1]+1);
	if (abs(st[i-1].x-st[i].x)>st[i].t-st[i-1].t) adder(-INF,min(st[i-1].x,st[i].x)-1,i),adder(min(st[i-1].x,st[i].x)+1,max(st[i-1].x,st[i].x)-1,i),adder(max(st[i-1].x,st[i].x)+1,INF,i);
    }
    s.clear(),s.insert((node){(int)(-INF),(int)(INF),0}),dp[0][0]=0;
    for (int i=1;i<=n;++i)
    {
	if (dp[lst[i]][0]+abs(st[lst[i]].x-st[i].x)<=st[lst[i]+1].t) Adder(dp[i][0],max(dp[lst[i]][0]+abs(st[lst[i]].x-st[i].x),st[lst[i]].t));
	if (dp[lst[i]][1]+abs(st[lst[lst[i]]].x-st[i].x)<=st[lst[i]+1].t) Adder(dp[i][0],max(dp[lst[i]][1]+abs(st[lst[lst[i]]].x-st[i].x),st[lst[i]].t));
	if (query(st[i].x)>=L[i]) dp[i][1]=st[lst[i]].t;
	//0
	if (i+1<=n)
	{
	    ps=i+1,l=st[ps].x-(st[ps].t-st[i].t),r=st[ps].x+(st[ps].t-st[i].t);
	    if (dp[i][0]+abs(st[i].x-st[ps].x)<=st[ps].t) d=(st[ps].t-abs(st[i].x-st[ps].x)-dp[i][0])>>1,sl=max(min(st[i].x,st[ps].x)-d,l),sr=min(max(st[i].x,st[ps].x)+d,r),adder(sl,sr,i+1);
	    if (dp[i][1]+abs(st[lst[i]].x-st[ps].x)<=st[ps].t) d=(st[ps].t-abs(st[lst[i]].x-st[ps].x)-dp[i][1])>>1,sl=max(min(st[lst[i]].x,st[ps].x)-d,l),sr=min(max(st[lst[i]].x,st[ps].x)+d,r),adder(sl,sr,i+1);
	}
	//1
	if (nt[i+1]<=n)
	{
	    ps=nt[i+1],ps2=i+1;
	    if (dp[i][0]+abs(st[i].x-st[ps2].x)<=st[ps2].t&&max(dp[i][0]+abs(st[i].x-st[ps2].x),st[i].t)+abs(st[ps2].x-st[ps].x)<=st[ps].t) adder(st[ps2].x,st[ps2].x,i+1);
	    if (dp[i][1]+abs(st[lst[i]].x-st[ps2].x)<=st[ps2].t&&max(dp[i][1]+abs(st[lst[i]].x-st[ps2].x),st[i].t)+abs(st[i].x-st[ps].x)<=st[ps].t) adder(st[ps2].x,st[ps2].x,i+1);
	}
    }
    puts((dp[n][0]!=inf||dp[n][1]!=inf)?"YES":"NO");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 2ms
memory: 3392kb

input:

5
2 1
3 2
9 6
10 5
13 -1

output:

NO

result:

ok single line: 'NO'

Test #2:

score: -5
Wrong Answer
time: 2ms
memory: 3396kb

input:

5
1 1
3 2
4 -1
6 4
10 -1

output:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #91:

score: 20
Accepted
time: 8ms
memory: 3768kb

input:

5000
6 6
80 80
170 48
240 106
243 179
329 176
412 93
485 176
552 249
555 316
613 371
650 313
733 251
735 253
736 334
815 254
893 333
943 255
965 227
1022 284
1116 205
1174 320
1230 376
1318 378
1336 288
1430 212
1494 276
1562 344
1597 309
1638 350
1716 272
1793 349
1809 365
1908 306
1951 464
2037 42...

output:

YES

result:

ok single line: 'YES'

Test #92:

score: 0
Accepted
time: 8ms
memory: 3664kb

input:

5000
64 -64
146 -46
177 -14
249 -5
327 -77
370 -83
438 -194
463 -219
554 -126
625 -199
689 -128
774 -50
854 -135
882 2
916 30
936 -12
1022 -98
1071 -32
1157 -49
1195 75
1206 37
1221 86
1227 77
1251 71
1269 101
1324 83
1373 28
1426 77
1439 24
1454 11
1508 -4
1601 35
1619 -58
1668 17
1719 -32
1775 -37...

output:

YES

result:

ok single line: 'YES'

Test #93:

score: -20
Wrong Answer
time: 3ms
memory: 3644kb

input:

5000
136 32
137 31
188 82
248 142
266 -52
277 124
327 135
370 185
445 153
506 228
536 214
586 194
652 128
685 244
778 95
812 2
884 108
917 141
984 36
989 208
1012 190
1042 213
1078 220
1139 184
1204 245
1205 311
1208 310
1282 382
1363 463
1383 308
1449 443
1470 530
1531 509
1560 591
1588 620
1623 55...

output:

NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%