Submission #967137

#	Time	Username	Problem	Language	Result	Execution time	Memory
967137		jamesbamber	Seats (IOI18_seats)	C++17	25 / 100	4042 ms	95400 KiB

seats

    #include "seats.h"
    #include <bits/stdc++.h>
    using namespace std;
     
     
    struct segment{
        vector<int> mn, mx;
     
        void build(int v, int l, int r, vector<int> &vec){
            if(r-l == 1){
                mn[v] = vec[l], mx[v] = vec[l];
                return;
            }
            int m = (l+r)/2;
            build(2*v, l, m, vec);
            build(2*v+1, m, r, vec);
            mn[v] = min(mn[2*v], mn[2*v+1]);
            mx[v] = max(mx[2*v], mx[2*v+1]);
        }
     
        segment(){}
     
        segment(int sz, vector<int> &vec){
            mn.resize(4*sz, INT_MAX), mx.resize(4*sz, -1);
            build(1, 0, sz, vec);
        }
     
        void upd(int v, int l, int r, int pos, int val){
            if(r-l == 1){
                mn[v] = val;
                mx[v] = val;
                return;
            }
            int m = (l+r)/2;
            
            if(pos < m) upd(2*v, l, m, pos, val);
            else upd(2*v+1, m, r, pos, val);
     
            mn[v] = min(mn[2*v], mn[2*v+1]);
            mx[v] = max(mx[2*v], mx[2*v+1]);
        }
     
        pair<int,int> query(int v, int l, int r, int ql, int qr){
            if(l >= qr or r <= ql) return {INT_MAX, -1};
            if(l >= ql and r <= qr) return {mn[v], mx[v]};
            int m = (l+r)/2;
            
            auto left = query(2*v, l, m, ql, qr);
            auto right = query(2*v+1, m, r, ql, qr);
     
            return {min(left.first, right.first), max(left.second, right.second)};
        }
     
        int greater(int v, int l, int r, int ql, int qr, int x){
            if(l >= qr or r <= ql) return -1;
            if(mx[v] <= x) return -1;
            if(r-l == 1) return l;
            int m = (l+r)/2;
     
            int y = greater(2*v, l, m, ql, qr, x);
            if(y == -1) y = greater(2*v+1, m, r, ql, qr, x);
            return y;
        }
     
        int smaller(int v, int l, int r, int ql, int qr, int x){
            if(l >= qr or r <= ql) return -1;
            if(mn[v] >= x) return -1;
            if(r-l == 1) return l;
            int m = (l+r)/2;
     
            int y = smaller(2*v, l, m, ql, qr, x);
            if(y == -1) y = smaller(2*v+1, m, r, ql, qr, x);
            return y;
        }
    };
     
    vector<int> px, py;
    set<int> changes;
    segment stx, sty;
    int h, w;
     
    void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
        for(int i=0; i<H*W; i++) px.push_back(R[i]), py.push_back(C[i]);
        h = H, w = W;
     
        stx = segment(h*w, px);
        sty = segment(h*w, py);
    }
     
     
    int swap_seats(int a, int b){
        swap(px[a], px[b]); swap(py[a], py[b]);
        stx.upd(1, 0, h*w, a, px[a]);
        sty.upd(1, 0, h*w, a, py[a]);
        stx.upd(1, 0, h*w, b, px[b]);
        sty.upd(1, 0, h*w, b, py[b]);
     
        vector<int> changes;
        int curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = stx.greater(1, 0, h*w, curr+1, h*w, px[curr]);
        }
        curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = stx.smaller(1, 0, h*w, curr+1, h*w, px[curr]);
        }
     
        curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = sty.greater(1, 0, h*w, curr+1, h*w, py[curr]);
        }
        curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = sty.smaller(1, 0, h*w, curr+1, h*w, py[curr]);
        }
     
        sort(changes.begin(), changes.end());
        changes.resize(unique(changes.begin(), changes.end())-changes.begin());
     
        assert(changes.size() <= h+w);
     
        int ans = 0;
        int prev = -2, prevpos = -1;
        for(int x: changes){
            if(prev >= prevpos+1 and prev < x+1) ans++;
            auto [mnx, mxx] = stx.query(1, 0, h*w, 0, x+1);
            auto [mny, mxy] = sty.query(1, 0, h*w, 0, x+1);
     
            prev = (mxx-mnx+1)*(mxy-mny+1);
            prevpos = x;
        }
     
        if(prev >= prevpos+1) ans++;
        return ans;
    }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from seats.cpp:2:
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:124:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |         assert(changes.size() <= h+w);
      |                ~~~~~~~~~~~~~~~^~~~~~

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