oj.uz

Submission #1109496

# Submission time Handle Problem Language Result Execution time Memory
1109496 2024-11-07T00:26:29 Z Dreamy_lovesper Curtains (NOI23_curtains) C++17
3 / 100
 16 ms 25220 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,g[mxn];
pll p[mxn];
vll graph[mxn];
struct Quest{
    ll l,r,id;
}Qu[mxn];
void Lovesper(const ll&TestCase){
    cin>>n>>m>>q;
    fu(i,1,m)cin>>p[i].fi>>p[i].se;
    fu(i,1,q){
        ll l,r;cin>>l>>r;
        Qu[i]={l,r,i};
    }
    struct Love12{
        function<void()>DreamyLove=[&](){
            vll f(n+7,0);
            fu(qq,1,q){
                auto[l,r,id]=Qu[qq];
                fu(i,1,n)f[i]=0;
                fu(i,1,n)
                    if(l<=p[i].fi&&p[i].se<=r){
                        f[p[i].fi]++;f[p[i].se+1]--;
                    }
                ll o=1;
                fu(i,l,r)o&=((f[i]+=f[i-1])>0);
                cout<<(o?"YES":"NO")<<'\n';
            }
        };
    };
    struct Love3{
        function<void()>DreamyLove=[&](){
            vector<vll>vec(n+7);
            vll f(n+7,0);
            fu(i,1,m)vec[p[i].fi].pb(p[i].se);
            if(n<=200)fu(i,1,n)sort(all(vec[i]));
            fu(qq,1,q){
                auto[l,r,id]=Qu[qq];
                fu(i,l-1,r+1)f[i]=0;
                fu(i,l,r){
                    auto j=upper_bound(all(vec[i]),r);
                    if(j==vec[i].begin())continue;
                    f[i]++;f[*(j-1)+1]--;
                }
                ll o=1;
                fu(i,l,r)o&=((f[i]+=f[i-1])>0);
                cout<<(o?"YES":"NO")<<'\n';
            }
        };
    };
    // if(n<=200&&m<=200&&q<=200)(new Love12())->DreamyLove();
    // else (new Love3())->DreamyLove();
    (new Love3())->DreamyLove();
}
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:55:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |          freopen((name+".test").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 4 ms 24912 KB Output is correct
2 Correct 4 ms 24912 KB Output is correct
3 Correct 5 ms 24912 KB Output is correct
4 Correct 5 ms 25080 KB Output is correct
5 Correct 5 ms 24912 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 5 ms 24912 KB Output is correct
8 Correct 5 ms 24912 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 24912 KB Output is correct
12 Correct 5 ms 24912 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 24912 KB Output is correct
3 Correct 5 ms 24912 KB Output is correct
4 Correct 5 ms 25080 KB Output is correct
5 Correct 5 ms 24912 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 5 ms 24912 KB Output is correct
8 Correct 5 ms 24912 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 24912 KB Output is correct
12 Correct 5 ms 24912 KB Output is correct
13 Incorrect 13 ms 25220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 24912 KB Output is correct
3 Correct 5 ms 24912 KB Output is correct
4 Correct 5 ms 25080 KB Output is correct
5 Correct 5 ms 24912 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 5 ms 24912 KB Output is correct
8 Correct 5 ms 24912 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 24912 KB Output is correct
12 Correct 5 ms 24912 KB Output is correct
13 Incorrect 13 ms 25220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25084 KB Output is correct
2 Correct 4 ms 24912 KB Output is correct
3 Correct 5 ms 25080 KB Output is correct
4 Correct 5 ms 25100 KB Output is correct
5 Incorrect 16 ms 25168 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 24912 KB Output is correct
3 Correct 5 ms 24912 KB Output is correct
4 Correct 5 ms 25080 KB Output is correct
5 Correct 5 ms 24912 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 5 ms 24912 KB Output is correct
8 Correct 5 ms 24912 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 24912 KB Output is correct
12 Correct 5 ms 24912 KB Output is correct
13 Incorrect 13 ms 25220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 24912 KB Output is correct
3 Correct 5 ms 24912 KB Output is correct
4 Correct 5 ms 25080 KB Output is correct
5 Correct 5 ms 24912 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 5 ms 24912 KB Output is correct
8 Correct 5 ms 24912 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 24912 KB Output is correct
12 Correct 5 ms 24912 KB Output is correct
13 Incorrect 13 ms 25220 KB Output isn't correct
14 Halted 0 ms 0 KB -