oj.uz

답안 #835608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835608 2023-08-23T16:36:27 Z mousebeaver 자리 배치 (IOI18_seats) C++14
37 / 100
 4000 ms 80808 KB 
    #include "seats.h"
    #include <bits/stdc++.h>
    #define pii pair<int, int>
    #define INF numeric_limits<int>::max()/2
    using namespace std;
     
    struct inf
    {
        int r1;
        int r2;
        int c1;
        int c2;
        bool possible;
    };
     
    inf combine(inf a, inf b)
    {
        return {min(a.r1, b.r1), max(a.r2, b.r2), min(a.c1, b.c1), max(a.c2, b.c2)};
    }
     
    int area(inf dat)
    {
        return ((1+dat.r2-dat.r1)*(1+dat.c2-dat.c1));
    }
     
    int left(int i)
    {
        return 2*i;
    }
     
    int right(int i)
    {
        return 2*i+1;
    }
     
    int par(int i)
    {
        return i/2;
    }
     
    inf query(int i, vector<inf>& s, int a, int b, int l, int r)
    {
        if(l <= a && b <= r)
        {
            return s[i];
        }
        if(r < a || b < l)
        {
            return {INF, 0, INF, 0};
        }
        int mid = (a+b)/2;
        inf q1 = query(left(i), s, a, mid, l, r);
        inf q2 = query(right(i), s, mid+1, b, l, r);
        return {min(q1.r1, q2.r1), max(q1.r2, q2.r2), min(q1.c1, q2.c1), max(q1.c2, q2.c2)};
    }
     
    void update(int i, vector<inf>& s, inf val)
    {
        s[i] = val;
        i = par(i);
        while(i > 0)
        {
            s[i] = {min(s[left(i)].r1, s[right(i)].r1), max(s[left(i)].r2, s[right(i)].r2), min(s[left(i)].c1, s[right(i)].c1), max(s[left(i)].c2, s[right(i)].c2)};
            i = par(i);
        }
    }
     
    vector<inf> s(0);
    vector<pii> p(0);
    vector<inf> a(0);
    int segnodes = 1;
    int counter = 1;
    int n = 1;
    bool sub3 = false;
     
    void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
    {
        if(H <= 1000 && W <= 1000)
        {
            sub3 = true;
        }

        if(sub3)
        {
            n = H*W;   
            while(2*n > segnodes)
            {
                segnodes *= 2;
            } 
        
            s.assign(segnodes, {INF, 0, INF, 0});
            p.assign(n, {-1, -1});
            for(int i = 0; i < n; i++)
            {
                s[i+segnodes/2] = {R[i], R[i], C[i], C[i]};
                p[i] = {R[i], C[i]};
            }
            for(int i = segnodes/2-1; i > 0; i--)
            {
                s[i] = {min(s[left(i)].r1, s[right(i)].r1), max(s[left(i)].r2, s[right(i)].r2), min(s[left(i)].c1, s[right(i)].c1), max(s[left(i)].c2, s[right(i)].c2)};
            }
        }
        else
        {
            n = H*W;
            for(int i = 0; i < n; i++)
            {
                p.push_back({R[i], C[i]});
            }
        
            a = {{p[0].first, p[0].first, p[0].second, p[0].second, true}};
            for(int i = 1; i < n; i++)
            {
                a.push_back(a.back());
                a.back().r1 = min(a.back().r1, p[i].first);
                a.back().r2 = max(a.back().r2, p[i].first);
                a.back().c1 = min(a.back().c1, p[i].second);
                a.back().c2 = max(a.back().c2, p[i].second);
                a.back().possible = ((1+a.back().r2-a.back().r1)*(1+a.back().c2-a.back().c1) == i+1);
                counter += a.back().possible;
            }
        }
    }
     
    int swap_seats(int d, int b) 
    {
        if(sub3)
        {

            swap(p[d], p[b]);
            update(segnodes/2+d, s, {p[d].first, p[d].first, p[d].second, p[d].second});
            update(segnodes/2+b, s, {p[b].first, p[b].first, p[b].second, p[b].second});
        
            int output = 1;
            int ar = 1;
            
            while(ar < n)
            {
                int i = segnodes/2;
                inf dat = s[i];
                while(area(dat) <= ar)
                {
                    i = par(i);
                    dat = s[i];
                }
                dat = s[left(i)];
                i = right(i);
                //Now, we are in the lowest node that contains enough area! => Going back down
                while(left(i) < segnodes)
                {
                    if(area(combine(s[left(i)], dat)) > ar)
                    {
                        i = left(i);
                    }
                    else
                    {
                        dat = combine(dat, s[left(i)]);
                        i = right(i);
                    }
                }
                dat = combine(dat, s[i]);
                ar = area(dat);
                output += (ar == area(query(1, s, 1, segnodes/2, 1, ar)));
            }
            return output;
        }
        else
        {
            if(d > b)
            {
                swap(d, b);
            }
            swap(p[d], p[b]);
        
            for(int i = d; i <= b; i++)
            {
                counter -= a[i].possible;
                if(i == 0)
                {
                    a[i] = {p[0].first, p[0].first, p[0].second, p[0].second, true};
                }
                else
                {
                    a[i] = a[i-1];
                }
                a[i].r1 = min(a[i].r1, p[i].first);
                a[i].r2 = max(a[i].r2, p[i].first);
                a[i].c1 = min(a[i].c1, p[i].second);
                a[i].c2 = max(a[i].c2, p[i].second);
                a[i].possible = ((1+a[i].r2-a[i].r1)*(1+a[i].c2-a[i].c1) == i+1);
                counter += a[i].possible;
            }
        
            return counter;
        }
    }

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 37 ms 420 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 404 KB Output is correct
8 Correct 7 ms 432 KB Output is correct
9 Correct 7 ms 456 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 18 ms 448 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 37 ms 420 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 404 KB Output is correct
8 Correct 7 ms 432 KB Output is correct
9 Correct 7 ms 456 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 18 ms 448 KB Output is correct
13 Correct 15 ms 1404 KB Output is correct
14 Correct 13 ms 1412 KB Output is correct
15 Correct 177 ms 1208 KB Output is correct
16 Correct 173 ms 1208 KB Output is correct
17 Correct 174 ms 1208 KB Output is correct
18 Correct 1026 ms 1388 KB Output is correct
19 Correct 994 ms 1392 KB Output is correct
20 Correct 174 ms 1208 KB Output is correct
21 Correct 174 ms 1208 KB Output is correct
22 Correct 176 ms 1096 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 80808 KB Output is correct
2 Correct 392 ms 80808 KB Output is correct
3 Correct 3232 ms 80688 KB Output is correct
4 Correct 528 ms 64844 KB Output is correct
5 Correct 369 ms 64820 KB Output is correct
6 Correct 3276 ms 64824 KB Output is correct
7 Correct 3088 ms 64864 KB Output is correct
8 Correct 855 ms 64872 KB Output is correct
9 Correct 2385 ms 64824 KB Output is correct
10 Correct 2137 ms 64820 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1340 KB Output is correct
2 Correct 202 ms 8784 KB Output is correct
3 Correct 3765 ms 80804 KB Output is correct
4 Correct 213 ms 80680 KB Output is correct
5 Correct 464 ms 65288 KB Output is correct
6 Correct 468 ms 65416 KB Output is correct
7 Correct 468 ms 65332 KB Output is correct
8 Correct 457 ms 65444 KB Output is correct
9 Correct 465 ms 65448 KB Output is correct
10 Correct 461 ms 65420 KB Output is correct
11 Correct 467 ms 65448 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1916 KB Output is correct
2 Correct 27 ms 1972 KB Output is correct
3 Correct 180 ms 1968 KB Output is correct
4 Correct 1880 ms 2224 KB Output is correct
5 Correct 1729 ms 2416 KB Output is correct
6 Execution timed out 4040 ms 66440 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 37 ms 420 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 404 KB Output is correct
8 Correct 7 ms 432 KB Output is correct
9 Correct 7 ms 456 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 18 ms 448 KB Output is correct
13 Correct 15 ms 1404 KB Output is correct
14 Correct 13 ms 1412 KB Output is correct
15 Correct 177 ms 1208 KB Output is correct
16 Correct 173 ms 1208 KB Output is correct
17 Correct 174 ms 1208 KB Output is correct
18 Correct 1026 ms 1388 KB Output is correct
19 Correct 994 ms 1392 KB Output is correct
20 Correct 174 ms 1208 KB Output is correct
21 Correct 174 ms 1208 KB Output is correct
22 Correct 176 ms 1096 KB Output is correct
23 Correct 212 ms 80808 KB Output is correct
24 Correct 392 ms 80808 KB Output is correct
25 Correct 3232 ms 80688 KB Output is correct
26 Correct 528 ms 64844 KB Output is correct
27 Correct 369 ms 64820 KB Output is correct
28 Correct 3276 ms 64824 KB Output is correct
29 Correct 3088 ms 64864 KB Output is correct
30 Correct 855 ms 64872 KB Output is correct
31 Correct 2385 ms 64824 KB Output is correct
32 Correct 2137 ms 64820 KB Output is correct
33 Correct 14 ms 1340 KB Output is correct
34 Correct 202 ms 8784 KB Output is correct
35 Correct 3765 ms 80804 KB Output is correct
36 Correct 213 ms 80680 KB Output is correct
37 Correct 464 ms 65288 KB Output is correct
38 Correct 468 ms 65416 KB Output is correct
39 Correct 468 ms 65332 KB Output is correct
40 Correct 457 ms 65444 KB Output is correct
41 Correct 465 ms 65448 KB Output is correct
42 Correct 461 ms 65420 KB Output is correct
43 Correct 467 ms 65448 KB Output is correct
44 Correct 15 ms 1916 KB Output is correct
45 Correct 27 ms 1972 KB Output is correct
46 Correct 180 ms 1968 KB Output is correct
47 Correct 1880 ms 2224 KB Output is correct
48 Correct 1729 ms 2416 KB Output is correct
49 Execution timed out 4040 ms 66440 KB Time limit exceeded
50 Halted 0 ms 0 KB -