oj.uz

Submission #967137

# Submission time Handle Problem Language Result Execution time Memory
967137 2024-04-21T09:09:37 Z jamesbamber Seats (IOI18_seats) C++17
25 / 100
 4000 ms 95400 KB 
    #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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 37 ms 620 KB Output is correct
6 Correct 6 ms 600 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 8 ms 528 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 17 ms 604 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 37 ms 620 KB Output is correct
6 Correct 6 ms 600 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 8 ms 528 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 15 ms 1644 KB Output is correct
15 Correct 22 ms 1636 KB Output is correct
16 Execution timed out 4042 ms 1628 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 94856 KB Output is correct
2 Correct 396 ms 94920 KB Output is correct
3 Correct 3170 ms 94764 KB Output is correct
4 Correct 464 ms 94816 KB Output is correct
5 Correct 346 ms 94780 KB Output is correct
6 Correct 3285 ms 94728 KB Output is correct
7 Correct 2766 ms 94912 KB Output is correct
8 Correct 770 ms 94796 KB Output is correct
9 Correct 2760 ms 94888 KB Output is correct
10 Correct 2390 ms 94792 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1628 KB Output is correct
2 Correct 169 ms 9176 KB Output is correct
3 Correct 3560 ms 94796 KB Output is correct
4 Correct 208 ms 94808 KB Output is correct
5 Execution timed out 4030 ms 94980 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2008 KB Output is correct
2 Correct 32 ms 2004 KB Output is correct
3 Correct 184 ms 1744 KB Output is correct
4 Correct 1681 ms 2196 KB Output is correct
5 Correct 177 ms 3080 KB Output is correct
6 Correct 1556 ms 95388 KB Output is correct
7 Correct 1588 ms 95400 KB Output is correct
8 Correct 2315 ms 87204 KB Output is correct
9 Correct 532 ms 86952 KB Output is correct
10 Execution timed out 4026 ms 86948 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 600 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 37 ms 620 KB Output is correct
6 Correct 6 ms 600 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 8 ms 528 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 15 ms 1644 KB Output is correct
15 Correct 22 ms 1636 KB Output is correct
16 Execution timed out 4042 ms 1628 KB Time limit exceeded
17 Halted 0 ms 0 KB -