Submission #408690

#	Time	Username	Problem	Language	Result	Execution time	Memory
408690		MKopchev	Seats (IOI18_seats)	C++14	100 / 100	2473 ms	180744 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;

namespace {

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

}  // namespace

const int nmax=1e6+42;

int n,m;

pair<int,int> where[nmax];

vector< vector<int> > inp;

pair<int,int> cnt[nmax];

struct info
{
    pair<int,int> mini;
    pair<int,int> sum;
    int cnt_mini;
};

void print(string s,info a)
{
    cout<<s<<" -> ";cout<<a.mini.first<<" "<<a.mini.second<<" , "<<a.sum.first<<" "<<a.sum.second<<" , "<<a.cnt_mini<<endl;
}
info tree[4*nmax];

info my_merge(info a,info b)
{
    b.mini={b.mini.first+a.sum.first,b.mini.second+a.sum.second};

    if(a.mini==b.mini)
    {
        a.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
        a.cnt_mini+=b.cnt_mini;

        return a;
    }

    if(a.mini>b.mini)swap(a,b);

    a.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
    return a;
}
void update(int node,int l,int r,int pos,pair<int,int> val)
{
    if(l==r)
    {
        tree[node].mini=val;
        tree[node].sum=val;
        tree[node].cnt_mini=1;

        //cout<<"pos= "<<pos<<" node= "<<node;print(" tree",tree[node]);

        return;
    }

    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);

    /*
    cout<<"node= "<<node<<" l= "<<l<<" r= "<<r<<endl;

    print("tree[node*2]",tree[node*2]);
    print("tree[node*2+1]",tree[node*2+1]);
    print("tree[node]",tree[node]);

    cout<<"---"<<endl;
    */
}

int ask(int x,int y)
{
    if(0>x||x>=n||0>y||y>=m)return 1e9;
    return inp[x][y];
}

void eval(int x,int y)
{
    if(0>x||x>=n||0>y||y>=m)return;

    int cur[5]={0,0,0,0,0};

    int help;

    help=1+(ask(x-1,y-1)<inp[x][y])+(ask(x-1,y)<inp[x][y])+(ask(x,y-1)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x-1,y)<inp[x][y])+(ask(x-1,y+1)<inp[x][y])+(ask(x,y+1)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x,y-1)<inp[x][y])+(ask(x+1,y-1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x,y+1)<inp[x][y])+(ask(x+1,y+1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
    cur[help]++;

    cnt[inp[x][y]]={cur[1]-cur[2],cur[3]-cur[4]};

    update(1,0,n*m-1,inp[x][y],cnt[inp[x][y]]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    for(int i=0;i<4*nmax;i++)
    {
        tree[i].mini={10,10};
        tree[i].sum={10,10};
    }

    n=H;
    m=W;

    for(int t=0;t<n*m;t++)
    {
        int i=R[t];
        int j=C[t];

        while(inp.size()<=i)inp.push_back({});
        while(inp[i].size()<=j)inp[i].push_back(j);

        where[t]={i,j};
        inp[i][j]=t;
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            eval(i,j);
}

int swap_seats(int a, int b)
{
    swap(inp[where[a].first][where[a].second],inp[where[b].first][where[b].second]);
    swap(where[a],where[b]);

    for(int x=-1;x<=1;x++)
        for(int y=-1;y<=1;y++)
        {
            eval(where[a].first+x,where[a].second+y);
            eval(where[b].first+x,where[b].second+y);
        }

    //print("tree[1]",tree[1]);

    return tree[1].cnt_mini;
}
/*
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;
}
*/

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:135:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |         while(inp.size()<=i)inp.push_back({});
      |               ~~~~~~~~~~^~~
seats.cpp:136:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |         while(inp[i].size()<=j)inp[i].push_back(j);
      |               ~~~~~~~~~~~~~^~~
seats.cpp: At global scope:
seats.cpp:7:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
    7 | int read_int() {
      |     ^~~~~~~~

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