Submission #967133

#	Time	Username	Problem	Language	Result	Execution time	Memory
967133		jamesbamber	Seats (IOI18_seats)	C++17	25 / 100	4099 ms	74156 KiB

seats

    #include "seats.h"
    #include <bits/stdc++.h>
    using namespace std;
     
     
    struct segment{
        vector<int> mn, mx;
        int sz = 1;
     
        segment(){}
        segment(int n, vector<int> &v){
            while(sz < n) sz*=2;
            mn.resize(2*sz, INT_MAX);
            for(int i=0; i<n; i++) mn[i+sz] = v[i]; 
            for(int i=sz-1; i>0; i--) mn[i] = min(mn[2*i], mn[2*i+1]);
     
            mx.resize(2*sz, -1);
            for(int i=0; i<n; i++) mx[i+sz] = v[i]; 
            for(int i=sz-1; i>0; i--) mx[i] = max(mx[2*i], mx[2*i+1]);
        }
     
        void upd(int id, int x){
            int i = id + sz;
            mn[i] = x;
            for(i>>=1; i>0; i>>=1) mn[i] = min(mn[2*i], mn[2*i+1]);
            
            i = id + sz;
            mx[i] = x;
            for(i>>=1; i>0; i>>=1) mx[i] = max(mx[2*i], mx[2*i+1]);
        }
     
        pair<int,int> query(int lold, int rold){
            int ansmn = INT_MAX;
            int l = lold, r = rold;
            for(l+=sz, r+=sz; l < r; l>>=1, r>>=1){
                if(l&1) ansmn = min(ansmn, mn[l++]);
                if(r&1) ansmn = min(ansmn, mn[--r]);
            }
     
            int ansmx = -1;
            l = lold, r = rold;
            for(l+=sz, r+=sz; l < r; l>>=1, r>>=1){
                if(l&1) ansmx = max(ansmx, mx[l++]);
                if(r&1) ansmx = max(ansmx, mx[--r]);
            }
     
            return {ansmn, ansmx};
        }
     
     
        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;
    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(a, px[a]);
        sty.upd(a, py[a]);
        stx.upd(b, px[b]);
        sty.upd(b, py[b]);
     
        //for(int i=0; i<h*w; i++) cout << sty.query(i, i+1).first << " " <<  sty.query(i, i+1).second << " " << endl;
     
        vector<int> changes;
        int curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = stx.greater(1, 0, stx.sz, curr+1, h*w, px[curr]);
        }
        curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = stx.smaller(1, 0, stx.sz, curr+1, h*w, px[curr]);
        }
     
        curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = sty.greater(1, 0, sty.sz, curr+1, h*w, py[curr]);
        }
        curr = 0;
        while(curr != -1){
            changes.push_back(curr);
            curr = sty.smaller(1, 0, sty.sz, curr+1, h*w, py[curr]);
        }
     
        sort(changes.begin(), changes.end());
     
        int ans = 0;
        int prev = -2, prevpos = -1;
        for(int x: changes){
            if(x == prevpos) continue;
            if(prev >= prevpos+1 and prev < x+1) ans++;
            auto [mnx, mxx] = stx.query(0, x+1);
            auto [mny, mxy] = sty.query(0, x+1);
            prev = (mxx-mnx+1)*(mxy-mny+1);
            prevpos = x;
        }
     
        if(prev >= prevpos+1) ans++;
        return ans;
    }

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