oj.uz

답안 #921047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921047 2024-02-03T09:07:48 Z beepbeepsheep Trampoline (info1cup20_trampoline) C++17
0 / 100
 2000 ms 90676 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
const ll inf=1e15;
const ll maxn=2e5+5;

vector<ii> tramps;
ll lo[maxn],hi[maxn];
struct qry{
    ll r1,c1,r2,c2,id;
    qry(ll a,ll b, ll c, ll d, ll e){
    	r1=a,c1=b,r2=c,c2=d,id=e;
    }
};
vector<qry> queries;
void dnc(ll l, ll r, vector<ii> tramp, vector<qry> que){
    ll m=(l+r)>>1;
    cerr<<l<<' '<<r<<endl;
    if (l==r){
        sort(tramp.begin(),tramp.end());
        for (auto u:que){
            ll lpos=lower_bound(tramp.begin(),tramp.end(),make_pair(u.r1,u.c1))
            		-tramp.begin();
            ll rpos=upper_bound(tramp.begin(),tramp.end(),make_pair(u.r2,u.c2))
            		-tramp.begin();
            if (rpos-lpos==u.r2-u.r1) lo[u.id]=inf;
        }
        return;
    }
    vector<ii> lt,rt; // left tramp, right tramp
    vector<qry> lq,rq,uq; //left query, right query, useful query
    for (auto u:que){
        if (u.c1>m) rq.emplace_back(u.r1,u.c1,u.r2,u.c2,u.id);
        else if (u.c2<=m) lq.emplace_back(u.r1,u.c1,u.r2,u.c2,u.id);
        else uq.emplace_back(u.r1,u.c1,u.r2,u.c2,u.id);
    }
    for (auto u:tramp){
        if (u.second>m) rt.emplace_back(u.first+1,u.second);
        else lt.emplace_back(u);
    }
    vector<ll> lh(lt.size()),rh(rt.size()); // left tramp lowest height, right tramp highest height
    sort(lt.begin(),lt.end()); //eval highest trampolines first
    sort(rt.begin(),rt.end()); //eval lowest trampolines first
    for (int i=lt.size()-1;i>=0;i--){
        lh[i]=lt[i].first+1;
        ll pos=lower_bound(lt.begin(),lt.end(),make_pair(lt[i].first+1,lt[i].second))
        		-lt.begin();
        if (lt[pos].first==lt[i].first+1) lh[i]=lh[pos];
        cerr<<lh[i]<<' '<<lt[i].first<<' '<<lt[i].second<<endl;
    }
    for (int i=0;i<rt.size();i++){
        rh[i]=rt[i].first-1;
        ll pos=upper_bound(rt.begin(),rt.end(),make_pair(rt[i].first-1,rt[i].second))
        		-rt.begin();
        if (rt[pos].first==rt[i].first-1) rh[i]=rh[pos];
        cerr<<rh[i]<<' '<<rt[i].first<<' '<<rt[i].second<<endl;
    }
    vector<tuple<ll,ll,ll>> s,e;
    for (auto u:uq){
        ll pos=lower_bound(lt.begin(),lt.end(),make_pair(u.r1,u.c1))
        		-lt.begin();
        if (pos==lt.size() || u.r1!=lt[pos].first) lo[u.id]=u.r1;
        else lo[u.id]=lh[pos];
        pos=upper_bound(rt.begin(),rt.end(),make_pair(u.r2,u.c2))
        		-rt.begin();
        pos--;
        if (pos==-1 || u.r2!=rt[pos].first) hi[u.id]=u.r2;
        else hi[u.id]=rh[pos];
        cerr<<u.r2<<' '<<rt[pos].first<<endl;
        cerr<<u.id<<' '<<lo[u.id]<<' '<<hi[u.id]<<'x'<<endl;
    }
    for (auto &u:rt){
    	u.first-=1;
    }
    dnc(l,m,lt,lq);
    dnc(m+1,r,rt,rq);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll r,c,t;
    cin>>r>>c>>t;
    ll a,b;
    for (int i=1;i<=t;i++){
        cin>>a>>b;
        tramps.emplace_back(a,b);
    }
    ll q,e,d;
    cin>>q;
    for (int i=1;i<=q;i++){
        cin>>a>>b>>e>>d;
        if (a>e || b>d){
            lo[i]=-inf;
            continue;
        }
        queries.emplace_back(a,b,e,d,i);
    }
    dnc(1,c,tramps,queries);
    for (int i=1;i<=q;i++) cout<<(lo[i]>=hi[i]?"Yes":"No")<<endl;
    return 0;
}

Compilation message

trampoline.cpp: In function 'void dnc(long long int, long long int, std::vector<std::pair<long long int, long long int> >, std::vector<qry>)':
trampoline.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i=0;i<rt.size();i++){
      |                  ~^~~~~~~~~~
trampoline.cpp:64:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if (pos==lt.size() || u.r1!=lt[pos].first) lo[u.id]=u.r1;
      |             ~~~^~~~~~~~~~~

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 450 ms 4260 KB expected YES, found NO [5th token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2086 ms 25508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2020 ms 90676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2059 ms 9644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2049 ms 47808 KB Time limit exceeded
2 Halted 0 ms 0 KB -