oj.uz

Submission #985222

# Submission time Handle Problem Language Result Execution time Memory
985222 2024-05-17T13:05:13 Z oolimry Seats (IOI18_seats) C++17
25 / 100
 4000 ms 80300 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector<int> R;
vector<int> C;

int lv1[1100100 * 4];
int rv1[1100100 * 4];
int lv2[1100100 * 4];
int rv2[1100100 * 4];

void hupdate(int i, int s, int e, int in, int k){
    if(s == e){
        lv1[i] = k;
        rv1[i] = k;
        return;
    }

    int m = (s + e)/2;

    if(in <= m){
        hupdate(i * 2,s,m,in,k);
    }
    else{
        hupdate(i * 2 + 1,m + 1, e, in, k);
    }

    lv1[i] = min(lv1[i * 2], lv1[i * 2 + 1]);
    rv1[i] = max(rv1[i * 2], rv1[i * 2 + 1]);
}

pair<int,int> hquery(int i, int s, int e, int S, int E){
    if(S <= s && e <= E){
        return  {lv1[i],rv1[i]};
    }

    int m = (s + e)/2;

    pair<int,int> ii = {1100100100, -1};

    if(S <= m){
        pair<int,int> ii1 = hquery(i * 2,s,m,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }
    if(m < E){
        pair<int,int> ii1 = hquery(i * 2 + 1,m + 1,e,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }

    return ii;
}

void cupdate(int i, int s, int e, int in, int k){
    if(s == e){
        lv2[i] = k;
        rv2[i] = k;
        return;
    }

    int m = (s + e)/2;

    if(in <= m){
        cupdate(i * 2,s,m,in,k);
    }
    else{
        cupdate(i * 2 + 1,m + 1, e, in, k);
    }

    lv2[i] = min(lv2[i * 2], lv2[i * 2 + 1]);
    rv2[i] = max(rv2[i * 2], rv2[i * 2 + 1]);
}

pair<int,int> cquery(int i, int s, int e, int S, int E){
    if(S <= s && e <= E){
        return  {lv2[i],rv2[i]};
    }

    int m = (s + e)/2;

    pair<int,int> ii = {1100100100, -1};

    if(S <= m){
        pair<int,int> ii1 = cquery(i * 2,s,m,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }
    if(m < E){
        pair<int,int> ii1 = cquery(i * 2 + 1,m + 1,e,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }

    return ii;
}


int H,W;
int HW;

void give_initial_chart(int H_, int W_, std::vector<int> R_, std::vector<int> C_) {
    R = R_;
    C = C_;
    H = H_;
    W = W_;

    HW = H * W;

    for(int i = 0; i < H * W ; i++){
        hupdate(1,0,HW-1,i,R[i]);
        cupdate(1,0,HW-1,i,C[i]);
    }
}

int swap_seats(int a, int b) {
    swap(R[a],R[b]);
    swap(C[a],C[b]);

    hupdate(1,0,HW-1,a,R[a]);
    hupdate(1,0,HW-1,b,R[b]);

    cupdate(1,0,HW-1,a,C[a]);
    cupdate(1,0,HW-1,b,C[b]);


    int num = 2;

    int v = 2;
    int s = 1;
    int e = 1;

    while(v < H * W){
        pair<int,int> ii = hquery(1,0,HW-1,0, v - 1);
        pair<int,int> ii1 = cquery(1,0,HW-1,0, v - 1);

        s = (ii.second - ii.first + 1);
        e = (ii1.second - ii1.first + 1);

        if( s * e == v ){
            v = min( (s + 1) * e, s * (e + 1) );
            num++;
        }

        v = max(v, s * e);
    }

    return num;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6784 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 28 ms 6716 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 6 ms 6748 KB Output is correct
9 Correct 6 ms 6696 KB Output is correct
10 Correct 4 ms 6744 KB Output is correct
11 Correct 4 ms 6564 KB Output is correct
12 Correct 22 ms 6720 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6784 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 28 ms 6716 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 6 ms 6748 KB Output is correct
9 Correct 6 ms 6696 KB Output is correct
10 Correct 4 ms 6744 KB Output is correct
11 Correct 4 ms 6564 KB Output is correct
12 Correct 22 ms 6720 KB Output is correct
13 Correct 11 ms 7000 KB Output is correct
14 Correct 9 ms 7004 KB Output is correct
15 Correct 9 ms 7032 KB Output is correct
16 Execution timed out 4041 ms 7004 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 78928 KB Output is correct
2 Correct 459 ms 79256 KB Output is correct
3 Correct 2850 ms 79088 KB Output is correct
4 Correct 471 ms 78928 KB Output is correct
5 Correct 459 ms 78924 KB Output is correct
6 Correct 3688 ms 78932 KB Output is correct
7 Correct 1287 ms 79100 KB Output is correct
8 Correct 657 ms 79184 KB Output is correct
9 Correct 2575 ms 79320 KB Output is correct
10 Correct 2147 ms 78972 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7004 KB Output is correct
2 Correct 72 ms 14172 KB Output is correct
3 Correct 2162 ms 79052 KB Output is correct
4 Correct 398 ms 79104 KB Output is correct
5 Execution timed out 4049 ms 78932 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8292 KB Output is correct
2 Correct 21 ms 8152 KB Output is correct
3 Correct 212 ms 8160 KB Output is correct
4 Correct 2845 ms 8296 KB Output is correct
5 Correct 69 ms 8540 KB Output is correct
6 Correct 2246 ms 80020 KB Output is correct
7 Correct 2170 ms 80300 KB Output is correct
8 Correct 1861 ms 79952 KB Output is correct
9 Correct 523 ms 79940 KB Output is correct
10 Execution timed out 4102 ms 80008 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 6744 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6784 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 28 ms 6716 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 6 ms 6748 KB Output is correct
9 Correct 6 ms 6696 KB Output is correct
10 Correct 4 ms 6744 KB Output is correct
11 Correct 4 ms 6564 KB Output is correct
12 Correct 22 ms 6720 KB Output is correct
13 Correct 11 ms 7000 KB Output is correct
14 Correct 9 ms 7004 KB Output is correct
15 Correct 9 ms 7032 KB Output is correct
16 Execution timed out 4041 ms 7004 KB Time limit exceeded
17 Halted 0 ms 0 KB -