Submission #611268

#	Time	Username	Problem	Language	Result	Execution time	Memory
611268		Cross_Ratio	Seats (IOI18_seats)	C++14	0 / 100	240 ms	40284 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;
typedef pair<int,int> P;
struct SegTree {
    struct Node {
        int sum[3];//0, 1, 2
        int cnt;
        Node(int _c, int s1, int s2, int s3) {
            cnt = _c;
            sum[0] = s1;
            sum[1] = s2;
            sum[2] = s3;
        }
        Node() {
            cnt = sum[0] = sum[1] = sum[2] = 0;
        }
    };
    vector<Node> seg; // max, min
    int MAX;
    void init(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    Node f(Node x, Node y, int cnt) {
        Node c;
        c.cnt = cnt;
        c.sum[0] = c.sum[1] = c.sum[2] = 0;
        for(int i = 0; i+cnt < 3; i++) {
            c.sum[i+cnt] += x.sum[i] + y.sum[i];
        }
        return c;
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].cnt += k;
        }
        else {
            int mid = ns + ne >> 1;
            add(s,e,k,2*n,ns,mid);
            add(s,e,k,2*n+1,mid,ne);
        }
        assert(seg[n].cnt >= 0);
        if(ne==ns+1) {
            seg[n].sum[0] = seg[n].sum[1] = seg[n].sum[2] = 0;
            if(seg[n].cnt < 3) seg[n].sum[seg[n].cnt] = 1;
        }
        else {
            seg[n] = f(seg[2*n],seg[2*n+1], seg[n].cnt);
        }
    }
    void add(int s, int e, int k) {
        add(s,e,k,1,0,MAX/2);
    }
    int sum() {
        return seg[1].sum[2];
    }
};
//int chk[1000005];
SegTree tree;
int B[1000005];
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;
    }
    for(i=0;i<W;i++) B[C[i]] =i;
    tree.init(W+3);
    for(i=0;i+1<W;i++) {
        int a = min(B[i],B[i+1]);
        int b = max(B[i],B[i+1]);
        tree.add(a, b, 1);
    }
    tree.add(B[0], W, 1);
    tree.add(B[W-1], W, 1);
}
int dx[2] = {1,-1};
bool in(int x) {
    return 0 <=x && x < W;
}
int swap_seats(int a, int b) {
    if(C[a]>C[b]) swap(a, b);
    if(1==0) {
        int i;
        for(i=0;i<1;i++) {
            int a2 = C[a]  - 1;
            if(in(a2)) {
                tree.add(min(a,B[a2]),max(a,B[a2]),-1);
            }
            else {
                tree.add(a, W, -1);
            }
        }
        for(i=0;i<1;i++) {
            int b2 = C[b] + 1;
            if(in(b2)) {
                tree.add(min(b,B[b2]),max(b,B[b2]),-1);
            }
            else {
                tree.add(b, W, -1);
            }
        }
        int v = B[C[b]];
        B[C[b]] = B[C[a]];
        B[C[a]] = v;
        v = C[a];
        C[a] = C[b];
        C[b] = v;
        for(i=0;i<1;i++) {
            int a2 = C[a] + 1;
            if(in(a2)) {
                tree.add(min(a,B[a2]),max(a,B[a2]),1);
            }
            else {
                tree.add(a, W, 1);
            }
        }
        for(i=0;i<1;i++) {
            int b2 = C[b] - 1;
            if(in(b2)) {
                tree.add(min(b,B[b2]),max(b,B[b2]),1);
            }
            else {
                tree.add(b, W, 1);
            }
        }
    }
    else {
        int i;
        for(i=0;i<2;i++) {
            int a2 = C[a] + dx[i];
            if(in(a2)) {
                tree.add(min(a,B[a2]),max(a,B[a2]),-1);
            }
            else {
                tree.add(a, W, -1);
            }
        }
        for(i=0;i<2;i++) {
            int b2 = C[b] + dx[i];
            if(in(b2)) {
                tree.add(min(b,B[b2]),max(b,B[b2]),-1);
            }
            else {
                tree.add(b, W, -1);
            }
        }
        int v = B[C[b]];
        B[C[b]] = B[C[a]];
        B[C[a]] = v;
        v = C[a];
        C[a] = C[b];
        C[b] = v;
        for(i=0;i<2;i++) {
            int a2 = C[a] + dx[i];
            if(in(a2)) {
                tree.add(min(a,B[a2]),max(a,B[a2]),1);
            }
            else {
                tree.add(a, W, 1);
            }
        }
        for(i=0;i<2;i++) {
            int b2 = C[b] + dx[i];
            if(in(b2)) {
                tree.add(min(b,B[b2]),max(b,B[b2]),1);
            }
            else {
                tree.add(b, W, 1);
            }
        }
    }
    return tree.sum();
}

Compilation message (stderr)

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

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