QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188658 | #4906. 球球 | _set_ | 0 | 1ms | 7588kb | C++20 | 7.1kb | 2023-09-26 10:23:46 | 2023-09-26 10:23:46 |
answer
/*
君は瞬きと共に過ぎてく時間も
遠くから見てると微笑んで
*/
/*author::ღꦿ࿐(DeepSea.) */
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define ll long long
#define lll __int128_t
#define lb long double
#define D double
#define mkp make_pair
#define Array vector<int>
#define Pair pair<int,int>
#define rep(variable,leftrange,rightrange) for(int variable=leftrange;variable<=rightrange;++variable)
#define Rep(variable,leftrange,rightrange) for(int variable=leftrange;variable>=rightrange;--variable)
#define Find(a,b) (lower_bound(a.begin(),a.end(),b)-a.begin())
#define Uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define All(x) x.begin(),x.end()
#define nxtl puts("")
#define sq(x) ((x)*(x))
#define Hash __gnu_pbds::gp_hash_table
#define PQ __gnu_pbds::priority_queue
#ifdef DEBUG
#define react puts("reacting now !")
#define debug(x) cout << #x << " = " << x << "\n"
#define debug2(l,r) cout << "[" #l "," #r "] = [" << l << "," << r << "]\n"
#define debug3(x,y,z) cout << "{" #x "," #y "," #z "} = " << "{" << x << "," << y << "," << z << "}\n"
#define debug_vec(v) cout << #v": size= " << v.size() << "\nelement: " ; for(auto p:v) cout << p << " "
#define FileIO(x) 6
#else
#define react 6
#define debug(x) 6
#define debug2(l,r) 6
#define debug3(x,y,z) 6
#define debug_vec(v) 6
#define FileIO(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#endif
namespace IO{
#define MAXSIZE (1<<20)
char *IO___p1=NULL,*IO___p2=NULL,IO___buf[MAXSIZE];
#ifdef DEBUG
#define gchar() getchar()
#else
#define gchar() (IO___p1==IO___p2&&(IO___p2=(IO___p1=IO___buf)+fread(IO___buf,1,MAXSIZE,stdin),IO___p1==IO___p2)?EOF:*IO___p1++)
#endif
inline void read(char *x){
char ch=gchar();
while(ch==' '||ch=='\n'||ch=='\r')ch=gchar();
do *x++=ch,ch=gchar(); while(ch!=' '&&ch!='\n'&&ch!='\r');
*x='\0';
}
template<typename _Tp>inline void read(_Tp &x){
x=0;char ch=gchar();
for(;!isdigit(ch);ch=gchar());
for(;isdigit(ch);ch=gchar())x=(x<<1)+(x<<3)+(ch^48);
}
template<typename _Tp>inline void nread(_Tp &x){
x=0;_Tp f=1;char ch=gchar();
for(;!isdigit(ch);ch=gchar())ch=='-'&&(f=-1);
for(;isdigit(ch);ch=gchar())x=(x<<1)+(x<<3)+(ch^48);
x*=f;
}
template<typename _Tp,typename ...Args>
inline void read(_Tp &x,Args &...args){read(x),read(args...);}
template<typename _Tp,typename ...Args>
inline void nread(_Tp &x,Args &...args){nread(x),nread(args...);}
template<typename _Tp>inline void wrt(_Tp x){
if(x<0)x=-x,putchar('-');
if(x>9)wrt(x/10);
putchar(x%10+48);
}
inline void wrt(char ch){putchar(ch);}
inline void wrt(char *s){while(*s!='\0')putchar(*s++);}
inline void wrt(const char *s){while(*s!='\0')putchar(*s++);}
template<typename _Tp,typename ...Args>
inline void wrt(_Tp x,Args ...args){wrt(x),wrt(args...);}
inline void Read(pair<int,int> &x) { IO::read(x.first,x.second); }
inline void Read(vector<int> &v,int n){v.resize(n);for(auto &p:v) IO::read(p);}
inline void Wrt(pair<int,int> x,char c) { IO::wrt(x.first,' ',x.second,c); }
inline void Wrt(vector<int> v,char c){for(auto p:v) IO::wrt(p,c);}
#undef MAXSIZE
}
template<typename _Tp>inline _Tp Min(_Tp x,_Tp y){return x<y?x:y;}
template<typename _Tp>inline _Tp Max(_Tp x,_Tp y){return x>y?x:y;}
template<typename _Tp>inline void Add(_Tp &x,_Tp y,_Tp p){x+=y,(x>=p) && (x-=p);}
template<typename _Tp>inline void upmax(_Tp &x,_Tp y){if(y>x)x=y;}
template<typename _Tp>inline void upmin(_Tp &x,_Tp y){if(y<x)x=y;}
using namespace IO ;
const int N = 1000050;
using segset = vector < pair <int,int> > ;
segset s , t;
int n ;
int a[N] , x[N] ;
const int inf = 1e9 + 7 ;
void Fix(segset &seg) {
if(seg.empty( )) return ;
sort(All(seg)) ;
for(auto[l,r]:seg) {
assert(l <= r);
upmax(l,-inf) , upmin(r,inf) ;
}
int lp = inf + 1 , rp = -inf - 1 ;
segset nw;
for(auto[l,r]:seg) {
if(l > rp + 1) {
if(lp <= rp) nw.emplace_back(lp , rp);
lp = l , rp = r;
}
upmax(rp , r);
}
if(lp <= rp) nw.emplace_back(lp , rp) ;
seg = nw ;
}
signed main()
{
// segset tmp = {{2 , 3} , {4 , 5} , {8 , 12} ,{2 , 3} , {2 , 2} , {3 , 3}};
// Fix(tmp) ;
// for(auto[l,r]:tmp) {
// wrt(l,' ',r,'\n') ;
// }
read(n) ;
rep(i,1,n) {
nread(a[i] , x[i]) ;
}
s.emplace_back(0,0) ;
t.emplace_back(0,0);
rep(i,1,n) {
segset S , T ;
int tim = a[i] - a[i - 1] ;
for(auto[l,r]:s) {
// I : x[i - 1] , C:[l,r]
if(tim >= abs(x[i] - x[i - 1])) {
// first : I go to the pos . dont change C
S.emplace_back(l,r);
// second : I go to the pos . Change C
auto [lp,rp] = minmax({x[i] , x[i - 1]});
int rem = tim - abs(x[i] - x[i - 1]) ;
S.emplace_back(lp - rem / 2 , rp + rem / 2);
// I put C there And go away
T.emplace_back(x[i] - rem , x[i] + rem);
}
// C get the cake.
if(l<=x[i]&&x[i]<=r) {
T.emplace_back(x[i - 1] - tim , x[i - 1] + tim);
}
}
for(auto[l,r]:t) {
// I : [l,r] , C : x[i - 1]
// I just go there , in this problem (x distict) is unnecessary.
// So Considering I go there and put another C in the path .
// And Consider I put C there and Go away
if(l <= x[i] && x[i] <= r) {
int lp = x[i] - tim ;
if(lp < l) lp = l - (tim - (x[i] - l)) / 2;
int rp = x[i] + tim ;
if(rp > r) rp = r + (tim - (r - x[i])) / 2;
S.emplace_back(lp , rp) ;
lp = x[i] - tim ;
rp = x[i] + tim ;
T.emplace_back(lp , rp) ;
}
if(x[i] < l && x[i] >= l - tim) {
int lp = x[i] - (tim - (l - x[i]) ) / 2;
int rp = x[i] + tim;
if(rp > r) rp = r + (tim - (r - x[i])) / 2 ;
S.emplace_back(lp , rp) ;
lp = x[i] - (tim - (l - x[i])) ;
rp = x[i] + (tim - (l - x[i])) ;
T.emplace_back(lp , rp) ;
}
if(x[i] > r && x[i] <= r + tim) {
int rp = x[i] + (tim - (x[i] - r)) / 2 ;
int lp = x[i] - tim ;
if(lp < l) lp = l - (tim - (x[i] - l)) / 2 ;
S.emplace_back(lp,rp) ;
lp = x[i] - (tim - (x[i] - r)) ;
rp = x[i] + (tim - (x[i] - r)) ;
T.emplace_back(lp , rp) ;
}
}
s = S , t = T ;
Fix(s) , Fix(t) ;
}
if(s.size( ) || t.size( )) puts("Yes") ; else puts("No") ;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7588kb
input:
5 2 1 3 2 9 6 10 5 13 -1
output:
No
result:
wrong answer 1st lines differ - expected: 'NO', found: 'No'
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: 0
Wrong Answer
time: 0ms
memory: 7532kb
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:
wrong answer 1st lines differ - expected: 'YES', found: 'Yes'
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%