QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188658#4906. 球球_set_0 1ms7588kbC++207.1kb2023-09-26 10:23:462023-09-26 10:23:46

Judging History

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

  • [2023-09-26 10:23:46]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7588kb
  • [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%