Submission #125255

#	Time	Username	Problem	Language	Result	Execution time	Memory
125255		DanerZein	Seats (IOI18_seats)	C++14	0 / 100	446 ms	87136 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAX 1000000
#define lenghttree 4000100
using namespace std;
typedef pair<int,int> ii;
std::vector<ii> r;
int l;
vector<int>treecma(lenghttree),treecmi(lenghttree),treerma(lenghttree),treermi(lenghttree);
void initrmi(int node,int a,int b){
  //  ma=max(ma,node);
    if(a==b){
       // //<<a<<" "<<r[a].first<<" node: "<<node<<endl;
        treermi[node]=r[a].first;
      //  return;
    }
    else{
    initrmi(2*node+1,a,(a+b)/2);
    initrmi(2*node+2,(a+b)/2+1,b);
    treermi[node]=min(treermi[2*node+1],treermi[2*node+2]);
    }
}
int nodea=-1,nodeb=-1;
void query(int node,int a,int b,int p,int q){
    if(b<p or a>q) return ;
    if(p<=a and b<=q){
        if(nodea==-1)nodea=node;
        else nodeb=node;
        return;
    }
    query(2*node+2,(a+b)/2+1,b,p,q);
    query(2*node+1,a,(a+b)/2,p,q);

}
void updatermi(int node,int a,int b,int p,int val){
    if(p<a or b<p) return;
    if(a==b){
        //<<a<<" "<<val<<" node: "<<node<<endl;
        treermi[node]=val;
        return;
    }
    updatermi(2*node+1,a,(a+b)/2,p,val);
    updatermi(2*node+2,(a+b)/2+1,b,p,val);
    treermi[node]=min(treermi[2*node+1],treermi[2*node+2]);
}
void initrma(int node,int a,int b){
    if(a==b){
        treerma[node]=r[a].first;
        return;
    }
    initrma(2*node+1,a,(a+b)/2);
    initrma(2*node+2,(a+b)/2+1,b);
    treerma[node]=max(treerma[2*node+1],treerma[2*node+2]);
}
int queryrma(int node,int a,int b,int p,int q){
    if(q<a or b<p) return 0;
    if(p<=a and b<=q) return treerma[node];
    return max(queryrma(2*node+1,a,(a+b)/2,p,q), queryrma(2*node+2,(a+b)/2+1,b,p,q));
}
void updaterma(int node,int a,int b,int p,int val){
    if(p<a or b<p) return;
    if(a==b){
        treerma[node]=val;
        return;
    }
    updaterma(2*node+1,a,(a+b)/2,p,val);
    updaterma(2*node+2,(a+b)/2+1,b,p,val);
    treerma[node]=max(treerma[2*node+1],treerma[2*node+2]);
}
void initcmi(int node,int a,int b){
    if(a==b){
        treecmi[node]=r[a].second;
        return;
    }
    initcmi(2*node+1,a,(a+b)/2);
    initcmi(2*node+2,(a+b)/2+1,b);
    treecmi[node]=min(treecmi[2*node+1],treecmi[2*node+2]);
}
int querycmi(int node,int a,int b,int p,int q){
    if(q<a or b<p) return MAX;
    if(p<=a and b<=q) return treecmi[node];
    return min(querycmi(2*node+1,a,(a+b)/2,p,q),querycmi(2*node+2,(a+b)/2+1,b,p,q));
}
void updatecmi(int node,int a,int b,int p,int val){
    if(p<a or b<p) return;
    if(a==b){
        treecmi[node]=val;
        return;
    }
    updatecmi(2*node+1,a,(a+b)/2,p,val);
    updatecmi(2*node+2,(a+b)/2+1,b,p,val);
    treecmi[node]=min(treecmi[2*node+1],treecmi[2*node+2]);
}
void initcma(int node,int a,int b){
    ////<<a<<" "<<b<<endl;
    if(a==b){
        treecma[node]=r[a].second;
        return;
    }
    initcma(2*node+1,a,(a+b)/2);
    initcma(2*node+2,(a+b)/2+1,b);
    treecma[node]=max(treecma[2*node+1],treecma[2*node+2]);
}
int querycma(int node,int a,int b,int p,int q){
    if(q<a or b<p) return 0;
    if(p<=a and b<=q) return treecma[node];
    return max(querycma(2*node+1,a,(a+b)/2,p,q), querycma(2*node+2,(a+b)/2+1,b,p,q));
}
void updatecma(int node, int a,int b,int p,int val){

    if(p<a or b<p) return;
    if(a==b){//<<a<<" "<<b<<" "<<node<<" "<<val<<endl;
        treecma[node]=val;
        return;
    }
    updatecma(2*node+1,a,(a+b)/2,p,val);
    updatecma(2*node+2,(a+b)/2+1,b,p,val);
    treecma[node]=max(treecma[2*node+1],treecma[2*node+2]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
 //<<endl;
  for(int i=0;i<R.size();i++){
    r.push_back(ii(R[i],C[i]));
  }
  /*for(int i=0;i<R.size();i++){
    //<<r[i].first<<" "<<r[i].second<<endl;
  }*/
  l=R.size()-1;

  initcma(0,0,l);
////<<l<<endl;
  initcmi(0,0,l);
  initrma(0,0,l);
  initrmi(0,0,l);
  /*for(int i=0;i<ma;i++){
    //<<treermi[i]<<" ";
  }
  //<<endl;*/
}

int swap_seats(int a, int b) {
  int beautiful=0,a1,b1;
  a1=a;
  b1=b;
  /*for(int i=0;i<ma;i++){
    cout<<treecma[i]<<" ";
  }
  cout<<endl;*/
  updatecma(0,0,l,a1,r[b1].second);
  updatecma(0,0,l,b1,r[a1].second);
  updatecmi(0,0,l,b1,r[a1].second);
  updatecmi(0,0,l,a1,r[b1].second);
  updaterma(0,0,l,a1,r[b1].first);
  updaterma(0,0,l,b1,r[a1].first);
  updatermi(0,0,l,a1,r[b1].first);
  updatermi(0,0,l,b1,r[a1].first);
  ////<<r[a1].first<<" "<<r[b1].second<<" "<<a1<<" "<<b1<<endl;
  /*for(int i=0;i<ma;i++){
    cout<<treecma[i]<<" ";
  }
  cout<<endl<<endl;*/
  swap(r[a],r[b]);
  int rmi,rma,cmi,cma;
  rma=cma=-1;
  rmi=cmi=MAX;
  bool sw=0;
  for(int i=0;i<r.size();i++){
    /*
    rmi=min(rmi,r[i].first);
    cmi=min(cmi,r[i].second);
    rma=max(rma,r[i].first);
    cma=max(cma,r[i].second);*/
   // if(sw==1){
//   nodeans=-1;
    nodea=-1;nodeb=-1;
    query(0,0,l,0,i);
   // sw=0;
    //}
    if(nodeb==-1){
        rma=treerma[nodea];
        cma=treecma[nodea];
        rmi=treermi[nodea];
        cmi=treecmi[nodea];
    }
    else{
        rma=max(treerma[nodea],treerma[nodeb]);
        cma=max(treecma[nodea],treecma[nodeb]);
        rmi=min(treermi[nodea],treermi[nodeb]);
        cmi=min(treecmi[nodea],treecmi[nodeb]);
    }
    /*vector<int>::iterator itcmi,itcma,itrma,itrmi;
    itcmi=find(treecmi.begin(),treecmi.end(),cmi);
    itcma=find(treecma.begin(),treecma.end(),cma);
    itrmi=find(treermi.begin(),treermi.end(),rmi);
    itrma=find(treerma.begin(),treerma.end(),rma);
    printf("Posiciones: pcmi: %d pcma: %d prmi: %d prma: %d \nValores: vcmi: %d vcma: %d vrmi: %d vrma: %d\n",itcmi-treecmi.begin(),itcma-treecma.begin(),itrmi-treermi.begin(),itrma-treerma.begin(),*itcmi,*itcma,*itrmi,*itrma);
    printf("Nodea: %d nodeb:%d tcmi: %d tcma: %d trmi: %d,trma: %d\n",nodea,nodeb,min(treecmi[nodea],treecmi[nodeb]),max(treecma[nodea],treecma[nodeb]),min(treermi[nodea],treermi[nodeb]),max(treerma[nodea],treerma[nodeb]));*/
    if((rma-rmi+1)*(cma-cmi+1)==i+1){
        beautiful++;
    }
    if((rma-rmi+1)*(cma-cmi+1)>i+1){
        sw=1;
        i=(rma-rmi+1)*(cma-cmi+1)-1;
        beautiful++;
    }
    //printf("cmi: %d cma: %d rmi: %d rma: %d i: %d i+1: %d== %d\n",cmi,cma,rmi,rma,i,i+1,(rma-rmi+1)*(cma-cmi+1));

  }
 // swap(r[a],r[b]);
  return beautiful;
}
/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; j++) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}*/
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
/*
3
4
*/

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<R.size();i++){
               ~^~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:167:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<r.size();i++){
               ~^~~~~~~~~
seats.cpp:166:8: warning: variable 'sw' set but not used [-Wunused-but-set-variable]
   bool sw=0;
        ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30