Submission #629783

#	Time	Username	Problem	Language	Result	Execution time	Memory
629783		Cross_Ratio	Seats (IOI18_seats)	C++14	100 / 100	1901 ms	123156 KiB

seats

//#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int H, W;
vector<int> R, C;
vector<vector<int>> A;
const int INF = 1e9;
struct SegTree {
    struct Node {
        int mi;
        int v;
        int p;
        Node(int _m, int _v, int _p) : mi(_m),v(_v),p(_p) {}
        Node() : mi(INF),v(0),p(0) {}
    };
    vector<Node> seg;
    int MAX;
    void init(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=MAX/2;i<MAX;i++) {
            seg[i].mi = 0;
            seg[i].v = 1;
        }
    }
    Node f(Node x, Node y) {
        if(x.mi>y.mi) return y;
        if(x.mi<y.mi) return x;
        x.v += y.v;
        return x;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = f(seg[2*i],seg[2*i+1]);
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].p) {
            seg[n].mi += seg[n].p;
            if(n<MAX/2) {
                seg[2*n].p += seg[n].p;
                seg[2*n+1].p += seg[n].p;
            }
            seg[n].p = 0;
        }
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].p += k;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s,e,k,2*n,ns,mid);
        add(s,e,k,2*n+1,mid,ne);
        if(n<MAX/2) seg[n] = f(seg[2*n],seg[2*n+1]);
    }
    Node sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return Node(INF,0,0);
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
    }
    int sum(int s, int e) {
        return sum(s,e,1,0,MAX/2).v;
    }
};
SegTree tree;
int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};
bool in(int x, int y) {
    return 0 <=x && x < H && 0 <= y && y < W;
}
int B[1000005];
void calc(int a, int b, bool inv, bool offline) {
    int i, j;
    vector<int> V;
    for(i=0;i<4;i++) {
        int a2 = a + dx[i];
        int b2 = b + dy[i];
        if(in(a2, b2)) V.push_back(A[a2][b2]);
        else V.push_back(H*W);
    }
    sort(V.begin(),V.end());
    int rev = (inv ? -1 : 1);
    if(offline) {
        B[V[0]]++;
        B[V[1]]--;
        B[V[2]]+=5;
        B[V[3]]-=5;
    }
    else {
        tree.add(V[0], V[1], 1*rev, 1, 0, tree.MAX/2);
        tree.add(V[2], V[3], 5*rev, 1, 0, tree.MAX/2);
    }
}
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
    H = _H;
    W = _W;
    R = _R;
    C = _C;
    A.resize(H);
    int i, j;
    for(i=0;i<H;i++) A[i].resize(W);
    for(i=0;i<R.size();i++) {
        A[R[i]][C[i]] = i;
    }
    tree.init(H*W+3);
    //tree.cons();
    for(i=-1;i<H;i++) {
        for(j=-1;j<W;j++) {
            calc(i, j, false, true);
        }
    }
    int MAX = tree.MAX;
    int sum2 = 0;
    for(i=0;i<H*W;i++) {
        sum2 += B[i];
        //tree.add(i, i+1, sum2, 1, 0, MAX/2);
        tree.seg[i+MAX/2].mi = sum2;
    }
    tree.cons();
}
void swapping(int a, int b) {
    swap(A[R[a]][C[a]],A[R[b]][C[b]]);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
}
int mx[4] = {0,0,-1,-1};
int my[4] = {0,-1,0,-1};
int swap_seats(int a, int b) {
    int i, j;
    swapping(a, b);
    for(i=0;i<4;i++) {
        calc(R[a]+mx[i], C[a]+my[i], false, false);
    }
    for(i=0;i<4;i++) {
        calc(R[b]+mx[i], C[b]+my[i], false, false);
    }
    swapping(a, b);
    for(i=0;i<4;i++) {
        calc(R[a]+mx[i], C[a]+my[i], true, false);
    }
    for(i=0;i<4;i++) {
        calc(R[b]+mx[i], C[b]+my[i], true, false);
    }
    swapping(a, b);
    return tree.sum(0, H*W);
}

Compilation message (stderr)

seats.cpp: In member function 'void SegTree::add(int, int, int, int, int, int)':
seats.cpp:57:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
seats.cpp: In member function 'SegTree::Node SegTree::sum(int, int, int, int, int)':
seats.cpp:66:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
seats.cpp: In function 'void calc(int, int, bool, bool)':
seats.cpp:81:12: warning: unused variable 'j' [-Wunused-variable]
   81 |     int i, j;
      |            ^
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(i=0;i<R.size();i++) {
      |             ~^~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:137:12: warning: unused variable 'j' [-Wunused-variable]
  137 |     int i, j;
      |            ^

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