oj.uz

Submission #967133

# Submission time Handle Problem Language Result Execution time Memory
967133 2024-04-21T08:58:20 Z jamesbamber Seats (IOI18_seats) C++17
25 / 100
 4000 ms 74156 KB 
    #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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 33 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 7 ms 604 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 16 ms 592 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 33 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 7 ms 604 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 16 ms 592 KB Output is correct
13 Correct 12 ms 1372 KB Output is correct
14 Correct 11 ms 1524 KB Output is correct
15 Correct 13 ms 1372 KB Output is correct
16 Execution timed out 4034 ms 1372 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 72792 KB Output is correct
2 Correct 383 ms 72796 KB Output is correct
3 Correct 3296 ms 72924 KB Output is correct
4 Correct 438 ms 72924 KB Output is correct
5 Correct 332 ms 72804 KB Output is correct
6 Correct 3392 ms 72800 KB Output is correct
7 Correct 2947 ms 72904 KB Output is correct
8 Correct 791 ms 73020 KB Output is correct
9 Correct 2671 ms 72772 KB Output is correct
10 Correct 2372 ms 72700 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1368 KB Output is correct
2 Correct 208 ms 8064 KB Output is correct
3 Correct 3880 ms 72800 KB Output is correct
4 Correct 194 ms 72904 KB Output is correct
5 Execution timed out 4099 ms 73436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1924 KB Output is correct
2 Correct 31 ms 2112 KB Output is correct
3 Correct 156 ms 2052 KB Output is correct
4 Correct 3159 ms 2172 KB Output is correct
5 Correct 125 ms 2764 KB Output is correct
6 Correct 1500 ms 73996 KB Output is correct
7 Correct 1489 ms 74104 KB Output is correct
8 Correct 2506 ms 73868 KB Output is correct
9 Correct 445 ms 74156 KB Output is correct
10 Execution timed out 4030 ms 74012 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 33 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 7 ms 604 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 16 ms 592 KB Output is correct
13 Correct 12 ms 1372 KB Output is correct
14 Correct 11 ms 1524 KB Output is correct
15 Correct 13 ms 1372 KB Output is correct
16 Execution timed out 4034 ms 1372 KB Time limit exceeded
17 Halted 0 ms 0 KB -