oj.uz

Submission #1109741

# Submission time Handle Problem Language Result Execution time Memory
1109741 2024-11-07T13:00:15 Z vjudge1 Curtains (NOI23_curtains) C++17
100 / 100
 1233 ms 129352 KB 
#include<bits/stdc++.h>

using namespace std;
namespace std {
    // #include<Love>
    using ll=long long;
    using str=string;
    using int128=__int128_t;
    using ld=long double;

    typedef unsigned int ui;
    typedef unsigned long long ull;

    #define Love<3 HerLoveForMeJustaDream
}

#define Lovesper_ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define pb push_back
#define all(c) c.begin(),c.end()
#define fi first
#define se second
#define debug cout<<"I Love You\n";
#define fu(i,a,b) for(ll i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define fa(i,s) for(auto&i:s)
#define Bitc(x,i) (((x)>>(i))&1)
#define _log(_x) 63-__builtin_clzll(_x)
#define LoveTime chrono::steady_clock::now().time_since_epoch().count()

const pll dxy4[]={{-1,0},{0,-1},{0,1},{1,0}};
const pll dxy8[]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
constexpr  ll Mod=1e9+7;
constexpr  ll mxn=1e6+7,mxm=3e3+7;
constexpr long long inf=(1ll<<31);
constexpr ll lnf=(1ll<<60);

struct __TS {
    ~__TS() {
        // cerr<<"Time elapsed: "<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
    }
}__ts;

mt19937 rng(LoveTime);

#define setup ((1<<3)-1>>1)
void OpenLove(const str&name){

    // I'm So Lonely. I am Trying To Get Out This Lonely With Her Love

    Lovesper_
    if(fopen((name+".inp").c_str(),"r")){
        // freopen((name+".test").c_str(),"r",stdin);
       freopen((name+".inp").c_str(),"r",stdin);
        freopen((name+".out").c_str(),"w",stdout);
    }
}
template<class X,class Y>bool maximize(X&x,const Y&y){X eps=1e-18;if(x+eps<y){x=y;return 1;}return 0;}
template<class X,class Y>bool minimize(X&x,const Y&y){X eps=1e-18;if(x>y+eps){x=y;return 1;}return 0;}

template <class Fun>class y_combinator_result {
    Fun fun_;
    public:
    template<class T>explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args>decltype(auto) operator()(Args &&...args) {return fun_(std::ref(*this), std::forward<Args>(args)...);}
};
template<class Fun>decltype(auto) y_combinator(Fun &&fun) {return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}

ostream&operator<<( std::ostream& dest, __int128_t value){
    ostream::sentry s(dest);__uint128_t tmp=value<0?-value:value;
    char buffer[128];char*d=end(buffer);
    do{d--;*d="0123456789"[tmp%10];tmp/=10;}while(tmp);
    if(value<0)d--,*d='-';ll len=end(buffer)-d;
    if(dest.rdbuf()->sputn(d,len)!=len)dest.setstate(ios_base::badbit);
    return dest;
}

struct custom_hash{
    size_t operator()(uint64_t x)const{
        static const uint64_t HashRand=LoveTime;
        x^=HashRand;return x^(x>>16);
}};

int64_t add(ll&a,ll b){a+=b;if(a>=Mod)a%=Mod;while(a<0)a+=Mod;return a;}
int64_t mul(ll a,ll b,ll mod){a=1ll*a*b%mod;return a;}
int64_t mpow(ll a,ll b,ll mod){ll ans=1;for(;b;b>>=1,a=mul(a,a,mod))if(b&1)ans=mul(ans,a,mod);return ans;}

ll n,m,q,f[4*mxn],lz[4*mxn],g[mxn];
vll graph[mxn];
vector<pll>Qu[mxn];
vll c[mxn];
void Lovesper(const ll&TestCase){
    cin>>n>>m>>q;
    fu(i,1,m){
        ll l,r;cin>>l>>r;
        c[r].pb(l);
    }
    auto PushLazy=[&](ll id){
        auto SoLazy=[&](ll idx,ll val){maximize(f[idx],val);maximize(lz[idx],val);};
        ll x=lz[id];lz[id]=0;
        SoLazy(id<<1,x);
        SoLazy(id<<1|1,x);
    };
    function<void(ll,ll,ll,ll,ll,ll)>update=[&](ll id,ll l,ll r,ll u,ll v,ll val){
        if(r<u||v<l)return;
        if(u<=l&&r<=v){
            maximize(f[id],val);
            maximize(lz[id],val);
            return;
        }
        PushLazy(id);
        ll m=l+(r-l)/2;
        update(id<<1,l,m,u,v,val);
        update(id<<1|1,m+1,r,u,v,val);
        f[id]=min(f[id<<1],f[id<<1|1]);
    };
    function<ll(ll,ll,ll,ll,ll)>get=[&](ll id,ll l,ll r,ll u,ll v){
        if(r<u||v<l)return lnf;
        if(u<=l&&r<=v)return f[id];
        PushLazy(id);
        ll m=l+(r-l)/2;
        return  min(get(id<<1,l,m,u,v),get(id<<1|1,m+1,r,u,v));
    };
    vll ans(q+7,0);
    fu(i,1,q){
        ll l,r;cin>>l>>r;
        Qu[r].pb({l,i});
    }
    fu(r,1,n){
        for(auto&l:c[r])update(1,1,n,l,r,l);
        for(auto&[l,id]:Qu[r])ans[id]=(get(1,1,n,l,r)==l);
    }
    fu(i,1,q)cout<<(ans[i]?"YES":"NO")<<'\n';
}
signed main(int argc, char const *argv[]){
    OpenLove("lovesper");
    int tt=1;
    // cin>>tt;
    for(ll i=1;i<=tt;i++){
        Lovesper(i);
        if(i<tt)cout<<'\n';
    }
    return false;
}

Compilation message

curtains.cpp:14:13: warning: ISO C++11 requires whitespace after the macro name
   14 |     #define Love<3 HerLoveForMeJustaDream
      |             ^~~~
curtains.cpp: In function 'std::ostream& operator<<(std::ostream&, __int128)':
curtains.cpp:75:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   75 |     if(value<0)d--,*d='-';ll len=end(buffer)-d;
      |     ^~
curtains.cpp:75:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   75 |     if(value<0)d--,*d='-';ll len=end(buffer)-d;
      |                           ^~
curtains.cpp: In function 'void OpenLove(const str&)':
curtains.cpp:56:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |        freopen((name+".inp").c_str(),"r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 72272 KB Output is correct
2 Correct 17 ms 72396 KB Output is correct
3 Correct 13 ms 72272 KB Output is correct
4 Correct 14 ms 72272 KB Output is correct
5 Correct 12 ms 72272 KB Output is correct
6 Correct 12 ms 72388 KB Output is correct
7 Correct 13 ms 72408 KB Output is correct
8 Correct 13 ms 72272 KB Output is correct
9 Correct 17 ms 72448 KB Output is correct
10 Correct 19 ms 72272 KB Output is correct
11 Correct 23 ms 72272 KB Output is correct
12 Correct 19 ms 72272 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 72272 KB Output is correct
2 Correct 17 ms 72396 KB Output is correct
3 Correct 13 ms 72272 KB Output is correct
4 Correct 14 ms 72272 KB Output is correct
5 Correct 12 ms 72272 KB Output is correct
6 Correct 12 ms 72388 KB Output is correct
7 Correct 13 ms 72408 KB Output is correct
8 Correct 13 ms 72272 KB Output is correct
9 Correct 17 ms 72448 KB Output is correct
10 Correct 19 ms 72272 KB Output is correct
11 Correct 23 ms 72272 KB Output is correct
12 Correct 19 ms 72272 KB Output is correct
13 Correct 28 ms 72528 KB Output is correct
14 Correct 26 ms 72476 KB Output is correct
15 Correct 27 ms 72692 KB Output is correct
16 Correct 24 ms 72528 KB Output is correct
17 Correct 21 ms 72528 KB Output is correct
18 Correct 25 ms 72688 KB Output is correct
19 Correct 25 ms 72528 KB Output is correct
20 Correct 20 ms 72528 KB Output is correct
21 Correct 25 ms 72528 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 72272 KB Output is correct
2 Correct 17 ms 72396 KB Output is correct
3 Correct 13 ms 72272 KB Output is correct
4 Correct 14 ms 72272 KB Output is correct
5 Correct 12 ms 72272 KB Output is correct
6 Correct 12 ms 72388 KB Output is correct
7 Correct 13 ms 72408 KB Output is correct
8 Correct 13 ms 72272 KB Output is correct
9 Correct 17 ms 72448 KB Output is correct
10 Correct 19 ms 72272 KB Output is correct
11 Correct 23 ms 72272 KB Output is correct
12 Correct 19 ms 72272 KB Output is correct
13 Correct 28 ms 72528 KB Output is correct
14 Correct 26 ms 72476 KB Output is correct
15 Correct 27 ms 72692 KB Output is correct
16 Correct 24 ms 72528 KB Output is correct
17 Correct 21 ms 72528 KB Output is correct
18 Correct 25 ms 72688 KB Output is correct
19 Correct 25 ms 72528 KB Output is correct
20 Correct 20 ms 72528 KB Output is correct
21 Correct 25 ms 72528 KB Output is correct
22 Correct 248 ms 90412 KB Output is correct
23 Correct 236 ms 94696 KB Output is correct
24 Correct 276 ms 95860 KB Output is correct
25 Correct 503 ms 102728 KB Output is correct
26 Correct 238 ms 92744 KB Output is correct
27 Correct 505 ms 100052 KB Output is correct
28 Correct 483 ms 102984 KB Output is correct
29 Correct 215 ms 92488 KB Output is correct
30 Correct 150 ms 90952 KB Output is correct
31 Correct 172 ms 91464 KB Output is correct
32 Correct 401 ms 96628 KB Output is correct
33 Correct 187 ms 93000 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 72272 KB Output is correct
2 Correct 13 ms 72288 KB Output is correct
3 Correct 16 ms 72508 KB Output is correct
4 Correct 12 ms 72272 KB Output is correct
5 Correct 14 ms 72644 KB Output is correct
6 Correct 16 ms 72528 KB Output is correct
7 Correct 20 ms 72528 KB Output is correct
8 Correct 172 ms 90952 KB Output is correct
9 Correct 183 ms 94536 KB Output is correct
10 Correct 391 ms 100848 KB Output is correct
11 Correct 163 ms 93768 KB Output is correct
12 Correct 142 ms 83136 KB Output is correct
13 Correct 137 ms 84152 KB Output is correct
14 Correct 112 ms 84040 KB Output is correct
15 Correct 122 ms 82400 KB Output is correct
16 Correct 133 ms 84552 KB Output is correct
17 Correct 122 ms 82512 KB Output is correct
18 Correct 853 ms 124308 KB Output is correct
19 Correct 929 ms 119908 KB Output is correct
20 Correct 751 ms 120336 KB Output is correct
21 Correct 746 ms 119764 KB Output is correct
22 Correct 777 ms 119112 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 72272 KB Output is correct
2 Correct 17 ms 72396 KB Output is correct
3 Correct 13 ms 72272 KB Output is correct
4 Correct 14 ms 72272 KB Output is correct
5 Correct 12 ms 72272 KB Output is correct
6 Correct 12 ms 72388 KB Output is correct
7 Correct 13 ms 72408 KB Output is correct
8 Correct 13 ms 72272 KB Output is correct
9 Correct 17 ms 72448 KB Output is correct
10 Correct 19 ms 72272 KB Output is correct
11 Correct 23 ms 72272 KB Output is correct
12 Correct 19 ms 72272 KB Output is correct
13 Correct 28 ms 72528 KB Output is correct
14 Correct 26 ms 72476 KB Output is correct
15 Correct 27 ms 72692 KB Output is correct
16 Correct 24 ms 72528 KB Output is correct
17 Correct 21 ms 72528 KB Output is correct
18 Correct 25 ms 72688 KB Output is correct
19 Correct 25 ms 72528 KB Output is correct
20 Correct 20 ms 72528 KB Output is correct
21 Correct 25 ms 72528 KB Output is correct
22 Correct 136 ms 77896 KB Output is correct
23 Correct 171 ms 78092 KB Output is correct
24 Correct 224 ms 82800 KB Output is correct
25 Correct 199 ms 82504 KB Output is correct
26 Correct 151 ms 83272 KB Output is correct
27 Correct 166 ms 84552 KB Output is correct
28 Correct 129 ms 83528 KB Output is correct
29 Correct 151 ms 83016 KB Output is correct
30 Correct 197 ms 82248 KB Output is correct
31 Correct 189 ms 82352 KB Output is correct
32 Correct 169 ms 82504 KB Output is correct
33 Correct 140 ms 84956 KB Output is correct
34 Correct 157 ms 81992 KB Output is correct
35 Correct 180 ms 82136 KB Output is correct
36 Correct 155 ms 82504 KB Output is correct
37 Correct 153 ms 82668 KB Output is correct
38 Correct 147 ms 82788 KB Output is correct
39 Correct 136 ms 83324 KB Output is correct
40 Correct 132 ms 82376 KB Output is correct
41 Correct 120 ms 82760 KB Output is correct
42 Correct 132 ms 82508 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 72272 KB Output is correct
2 Correct 17 ms 72396 KB Output is correct
3 Correct 13 ms 72272 KB Output is correct
4 Correct 14 ms 72272 KB Output is correct
5 Correct 12 ms 72272 KB Output is correct
6 Correct 12 ms 72388 KB Output is correct
7 Correct 13 ms 72408 KB Output is correct
8 Correct 13 ms 72272 KB Output is correct
9 Correct 17 ms 72448 KB Output is correct
10 Correct 19 ms 72272 KB Output is correct
11 Correct 23 ms 72272 KB Output is correct
12 Correct 19 ms 72272 KB Output is correct
13 Correct 28 ms 72528 KB Output is correct
14 Correct 26 ms 72476 KB Output is correct
15 Correct 27 ms 72692 KB Output is correct
16 Correct 24 ms 72528 KB Output is correct
17 Correct 21 ms 72528 KB Output is correct
18 Correct 25 ms 72688 KB Output is correct
19 Correct 25 ms 72528 KB Output is correct
20 Correct 20 ms 72528 KB Output is correct
21 Correct 25 ms 72528 KB Output is correct
22 Correct 248 ms 90412 KB Output is correct
23 Correct 236 ms 94696 KB Output is correct
24 Correct 276 ms 95860 KB Output is correct
25 Correct 503 ms 102728 KB Output is correct
26 Correct 238 ms 92744 KB Output is correct
27 Correct 505 ms 100052 KB Output is correct
28 Correct 483 ms 102984 KB Output is correct
29 Correct 215 ms 92488 KB Output is correct
30 Correct 150 ms 90952 KB Output is correct
31 Correct 172 ms 91464 KB Output is correct
32 Correct 401 ms 96628 KB Output is correct
33 Correct 187 ms 93000 KB Output is correct
34 Correct 12 ms 72272 KB Output is correct
35 Correct 13 ms 72288 KB Output is correct
36 Correct 16 ms 72508 KB Output is correct
37 Correct 12 ms 72272 KB Output is correct
38 Correct 14 ms 72644 KB Output is correct
39 Correct 16 ms 72528 KB Output is correct
40 Correct 20 ms 72528 KB Output is correct
41 Correct 172 ms 90952 KB Output is correct
42 Correct 183 ms 94536 KB Output is correct
43 Correct 391 ms 100848 KB Output is correct
44 Correct 163 ms 93768 KB Output is correct
45 Correct 142 ms 83136 KB Output is correct
46 Correct 137 ms 84152 KB Output is correct
47 Correct 112 ms 84040 KB Output is correct
48 Correct 122 ms 82400 KB Output is correct
49 Correct 133 ms 84552 KB Output is correct
50 Correct 122 ms 82512 KB Output is correct
51 Correct 853 ms 124308 KB Output is correct
52 Correct 929 ms 119908 KB Output is correct
53 Correct 751 ms 120336 KB Output is correct
54 Correct 746 ms 119764 KB Output is correct
55 Correct 777 ms 119112 KB Output is correct
56 Correct 136 ms 77896 KB Output is correct
57 Correct 171 ms 78092 KB Output is correct
58 Correct 224 ms 82800 KB Output is correct
59 Correct 199 ms 82504 KB Output is correct
60 Correct 151 ms 83272 KB Output is correct
61 Correct 166 ms 84552 KB Output is correct
62 Correct 129 ms 83528 KB Output is correct
63 Correct 151 ms 83016 KB Output is correct
64 Correct 197 ms 82248 KB Output is correct
65 Correct 189 ms 82352 KB Output is correct
66 Correct 169 ms 82504 KB Output is correct
67 Correct 140 ms 84956 KB Output is correct
68 Correct 157 ms 81992 KB Output is correct
69 Correct 180 ms 82136 KB Output is correct
70 Correct 155 ms 82504 KB Output is correct
71 Correct 153 ms 82668 KB Output is correct
72 Correct 147 ms 82788 KB Output is correct
73 Correct 136 ms 83324 KB Output is correct
74 Correct 132 ms 82376 KB Output is correct
75 Correct 120 ms 82760 KB Output is correct
76 Correct 132 ms 82508 KB Output is correct
77 Correct 1233 ms 129352 KB Output is correct
78 Correct 1231 ms 117356 KB Output is correct
79 Correct 899 ms 123196 KB Output is correct
80 Correct 889 ms 123148 KB Output is correct
81 Correct 802 ms 121612 KB Output is correct
82 Correct 937 ms 122440 KB Output is correct
83 Correct 1210 ms 117320 KB Output is correct
84 Correct 1218 ms 117340 KB Output is correct
85 Correct 1048 ms 118368 KB Output is correct
86 Correct 894 ms 116664 KB Output is correct
87 Correct 898 ms 123208 KB Output is correct
88 Correct 952 ms 121612 KB Output is correct