oj.uz

Submission #427047

# Submission time Handle Problem Language Result Execution time Memory
427047 2021-06-14T12:01:22 Z kai824 Trampoline (info1cup20_trampoline) C++17
100 / 100
 793 ms 48348 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define mp make_pair
#define f first
#define s second

pii pts[200005];
vector<int> disc;
map<int,int> mm;

vector<pii> vv[600005];
bool ans[200005];
vector<int> ss[200005];//set of nodes for each...

int par[200005];
int getr(int x){
  if(par[x]==-1)return x;
  return par[x]=getr(par[x]);
}
void merge(int a,int b){
  //if(par[a]!=-1 || par[b]!=-1)cerr<<"WTH\n";
  par[b]=a;
  // if(ss[a].size()<ss[b].size())swap(ss[a],ss[b]);
  // for()
}

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int r,c,n;
  cin>>r>>c>>n;//c is useless...

  int a,b,d;
  for(int i=0;i<n;i++){
    cin>>pts[i].f>>pts[i].s;
    disc.push_back(pts[i].f-1);
    disc.push_back(pts[i].f);
    disc.push_back(pts[i].f+1);
  }
  sort(disc.begin(),disc.end());
  disc.erase(unique(disc.begin(),disc.end()),disc.end());
  for(int i=0;i<disc.size();i++)mm[disc[i]]=i;
  for(int i=0;i<n;i++){
    pts[i].f=mm[pts[i].f];
    vv[pts[i].f].push_back(mp(pts[i].s,i));

    par[i]=-1;//ufds + set merging things here
    // ss[i].push_back(i);
  }
  for(int i=0;i<disc.size();i++){
    if(vv[i].size()>1)sort(vv[i].begin(),vv[i].end());
  }

  int q;
  cin>>q;
  int p;
  vector<pair<pii,pii> >qq;
  for(int i=0;i<q;i++){
    cin>>a>>b>>c>>d;//x y x y
    //cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';
    if(a>c){
      ans[i]=false;
      continue;
    }
    if(a==c){
      //cout<<i<<"THIS EXECUTED!\n";
      ans[i]=(b<=d);
      continue;
    }
    if(mm.find(a)==mm.end() || mm.find(c-1)==mm.end())continue;//leave as false...
    a=mm[a];c=mm[c-1];
    p=upper_bound(vv[c].begin(),vv[c].end(),mp(d,INT_MAX))-vv[c].begin();
    if(p==0)continue;
    if(vv[c][p-1].f<b)continue;
    p=vv[c][p-1].s;//the node to use...
    qq.emplace_back(mp(a,b),mp(p,i));
    //cout<<a<<' '<<b<<' '<<p<<' '<<i<<'\n';
  }
  sort(qq.begin(),qq.end());
  int last=disc.size()-1;//last row that has been "settled"...
  int clast=1e9;//c last...
  set<int> ss;
  for(int i=qq.size()-1;i>=0;i--){
    a=qq[i].f.f;b=qq[i].f.s;p=qq[i].s.f;
    if(a<last){
      while(last>a){
        int p1=vv[last-1].size()-1,p2=vv[last].size()-1;//point last to last-1...
        //if(last==2)cout<<"haha"<<p1<<' '<<p2<<'\n';
        while(p1>=0 && p2>=0){
          if(vv[last-1][p1].f<=vv[last][p2].f){
            merge(vv[last-1][p1].s,vv[last][p2].s);
            p2--;
          }else p1--;//it's too big, so reduce it...
        }

        last--;
      }
      clast=vv[a].size();
      ss.clear();
    }
    while(clast>0 && vv[a][clast-1].f>=b){
      clast--;
      ss.insert(getr(vv[a][clast].s));//getr of the node
    }
    ans[qq[i].s.s]=(ss.find(getr(p))!=ss.end());

  }
  for(int i=0;i<q;i++){
    if(ans[i])cout<<"Yes\n";
    else cout<<"No\n";
  }
  return 0;
}
/*
4 5 2
2 2
3 4
3
2 1 4 5
1 2 1 4
2 3 4 4
*/

Compilation message

trampoline.cpp: In function 'int32_t main()':
trampoline.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0;i<disc.size();i++)mm[disc[i]]=i;
      |               ~^~~~~~~~~~~~
trampoline.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=0;i<disc.size();i++){
      |               ~^~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19424 KB 200 token(s): yes count is 21, no count is 179
2 Correct 18 ms 19516 KB 200 token(s): yes count is 70, no count is 130
3 Correct 18 ms 19404 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 28604 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 146 ms 28436 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 138 ms 27656 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 159 ms 28460 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 35420 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 358 ms 33872 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 328 ms 32468 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 372 ms 33072 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 351 ms 33136 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 540 ms 36960 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 19716 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 21 ms 19640 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 25 ms 20592 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 21 ms 19676 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 21 ms 19808 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 18 ms 19796 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 39212 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 452 ms 36628 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 349 ms 33248 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 793 ms 48348 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 604 ms 41140 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 341 ms 36076 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 396 ms 36124 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 348 ms 33200 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 674 ms 39028 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 657 ms 39220 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 762 ms 43284 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 365 ms 36784 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 389 ms 36400 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 364 ms 35248 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 373 ms 34196 KB 200000 token(s): yes count is 129674, no count is 70326