Submission #125481

#	Time	Username	Problem	Language	Result	Execution time	Memory
125481		DanerZein	Seats (IOI18_seats)	C++14	5 / 100	4040 ms	104004 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAX 10000000
#define lenghttree 4000100
using namespace std;
typedef pair<int,int> ii;
std::vector<ii> r;
int l;
int ma=-1;
vector<int>nodes;
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){
        treermi[node]=r[a].first;
    }
    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 ;
    //cout<<a<<" "<<b<<" "<<node<<endl;
    if(a>=p and b<=q){

        nodes.push_back(node);
        return;
    }
    query(2*node+1,a,(a+b)/2,p,q);
    query(2*node+2,(a+b)/2+1,b,p,q);

}
void updatermi(int node,int a,int b,int p,int val){
    if(p<a or b<p) return;
    if(a==b){
        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]);
}
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]);
}
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){
    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]);
}
void updatecma(int node, int a,int b,int p,int val){

    if(p<a or b<p) return;
    if(a==b){
        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) {
  for(int i=0;i<R.size();i++){
    r.push_back(ii(R[i],C[i]));
  }
  l=R.size()-1;
  initcma(0,0,l);
  initcmi(0,0,l);
  initrma(0,0,l);
  initrmi(0,0,l);
}

int swap_seats(int a, int b) {
  int beautiful=0,a1,b1;
  a1=a;
  b1=b;
  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);
  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++){
    nodea=-1;nodeb=-1;
    nodes.clear();
    query(0,0,l,0,i);
    //cout<<"i: "<<i<<endl;
    for(int j=0;j<nodes.size();j++){
      //  cout<<nodes[j]<<" ";
        rma=max(rma,treerma[nodes[j]]);
        cma=max(cma,treecma[nodes[j]]);
        rmi=min(rmi,treermi[nodes[j]]);
        cmi=min(cmi,treecmi[nodes[j]]);
    }
    //cout<<endl;
   // cout<<nodea<<" "<<nodeb<<endl;
    //cout<<"i: "<<i<<" nodea: "<<nodea<<" nodeb: "<<nodeb<<endl;
    if((rma-rmi+1)*(cma-cmi+1)==i+1){
       // cout<<"i: "<<i+1<<endl;
        beautiful++;
    }
    if((rma-rmi+1)*(cma-cmi+1)>i+1){

        i=(rma-rmi+1)*(cma-cmi+1)-2;
        //cout<<"i: "<<i<<endl;
       // beautiful++;
    }
  }
  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:105: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:132:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<r.size();i++){
               ~^~~~~~~~~
seats.cpp:137:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<nodes.size();j++){
                 ~^~~~~~~~~~~~~
seats.cpp:131:8: warning: unused variable 'sw' [-Wunused-variable]
   bool sw=0;
        ^~

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