Submission #80177

#	Time	Username	Problem	Language	Result	Execution time	Memory
80177		zubec	Seats (IOI18_seats)	C++14	0 / 100	336 ms	46656 KiB

seats

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

std::vector<int> r;

const int SZ = 1000100;

pair<int, int> t[SZ*4];

int ob[SZ*4];

vector <vector<int> > arr;

void build(int v, int l, int r){
    if (l == r){
        t[v].second = 1;
        return;
    }
    int mid = (l+r)>>1;
    build(v+v, l, mid);
    build(v+v+1, mid+1, r);
    t[v].second = t[v+v].second + t[v+v+1].second;
}

void push(int v){
    if (ob[v] == 0)
        return;
    t[v+v].first += ob[v];
    t[v+v+1].first += ob[v];
    ob[v+v] += ob[v];
    ob[v+v+1] += ob[v];
    ob[v] = 0;
}

void update(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr)
        return;
    if (tl <= l && r <= tr){
        t[v].first += x;
        ob[v] += x;
        return;
    }
    int mid = (l+r)>>1;
    push(v);
    update(v+v, l, mid, tl, tr, x);
    update(v+v+1, mid+1, r, tl, tr, x);
    if (t[v+v].first < t[v+v+1].first){
        t[v] = t[v+v];
    } else
    if (t[v+v].first > t[v+v+1].first){
        t[v] = t[v+v+1];
    } else {
        t[v] = {t[v+v].first, t[v+v].second + t[v+v+1].second};
    }
}

int inf;

vector <int> R, C;

void upd(int pos1, int pos2, int x){
    int a = arr[0][pos1];
    int b = arr[0][pos2];
    if (a > b)
        swap(a, b);
    update(1, 1, inf, a+1, b, x);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    assert(H == 1);
    ::R = R;
    ::C = C;
    arr.resize(H, vector<int>(W+2, 0));
    for (int i = 0; i < H*W; i++){
        arr[R[i]][C[i]+1] = i;
    }
    inf = H*W;
    arr[0][0] = inf;
    arr[0].back() = inf;
    build(1, 1, inf);
    for (int i = 0; i + 1 < arr[0].size(); i++){
        upd(i, i+1, 1);
    }
}


int swap_seats(int a, int b) {
    int pos1 = C[a], pos2 = C[b];
    ++pos1;
    ++pos2;
    if (pos1 > pos2)
        swap(pos1, pos2);
    if (abs(pos1-pos2) != 1){
        upd(pos1-1, pos1, -1);
        upd(pos1, pos1+1, -1);
        upd(pos2-1, pos2, -1);
        upd(pos2, pos2+1, -1);
        swap(arr[0][pos1], arr[0][pos2]);
        upd(pos1-1, pos1, 1);
        upd(pos1, pos1+1, 1);
        upd(pos2-1, pos2, 1);
        upd(pos2, pos2+1, 1);
    } else {
        upd(pos1-1, pos1, -1);
        upd(pos1, pos1+1, -1);
        upd(pos2, pos2+1, -1);
        swap(arr[0][pos1], arr[0][pos2]);
        upd(pos1-1, pos1, 1);
        upd(pos1, pos1+1, 1);
        upd(pos2, pos2+1, 1);
    }
    return t[1].second;
}

/**
1 0 3 2

1 4 2
0 1
0 0
0 3
0 2
0 1
3 2

*/

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + 1 < arr[0].size(); i++){
                     ~~~~~~^~~~~~~~~~~~~~~

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