CSES - HIIT Open 2024 - Results
Submission details
Task:Key cutting
Sender:ä
Submission time:2024-11-16 14:40:01 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.00 sdetails
#3ACCEPTED0.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#8ACCEPTED0.00 sdetails
#90.03 sdetails
#100.03 sdetails
#110.03 sdetails
#120.03 sdetails
#130.04 sdetails
#140.04 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:45:18: warning: unused variable 'ok' [-Wunused-variable]
   45 |             bool ok = true;
      |                  ^~
input/code.cpp:47:17: warning: unused variable 'mi2' [-Wunused-variable]
   47 |             int mi2 = 1000000001;
      |                 ^~~

Code

#include <bits/stdc++.h>

// g++ -std=c++17 k.cpp -o k
using namespace std;
int s[10101010];
int n;
unordered_map<int, int> lahin;

int hae(int a, int b){
    a +=n; b+=n;
    int mi = 1000000001;
    while(a<=b){
        if(a%2==1) mi = min(mi, s[a++]);
        if(a%2==0) mi = min(mi, s[b--]);
        a/=2; b/=2;
    }
    return mi;
}
void add(int k, int x){
    k+=n;
    s[k]=x;
    for (k /=2; k>=1; k/=2){
        s[k] = min(s[k*2], s[k*2+1]);
    }
}

int main() {
     cin >> n;
    for (int i = 0; i < n;++i){
        int oof;
        cin >> oof;
        add(i, oof);
    }
    unordered_set<int> f;
    int cuts = 0;
    for (int i = 0; i < n; ++i){
        auto coun = lahin.count(s[i+n]);
        //cout << "etsitaaan " << s[i+n] << " " << coun << endl;
        if (coun==0){
            //cout << "ei loyd " << i << " " << s[i+n] << endl;
            cuts += 1;
            lahin[s[i+n]] = i;
        } else {
            auto lah = lahin[s[i+n]];
            bool ok = true;
            int mi = hae(lah+1, i);
            int mi2 = 1000000001;
            //for (int j = i-1; j > lah; --j){
            //    mi2 = min(mi2, s[j+n]);
            //}
            ///cout << "loyd " << mi << " " << s[i+n] << endl;
            if (mi < s[i+n]){
                //cout << "lis 1" << endl;
                cuts += 1;
            }
            lahin[s[i+n]] = i;
        }
    }
    cout << cuts << endl;
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
3
1 2 1

correct output
2

user output
2

Test 2

Verdict:

input
1
0

correct output
0

user output
1

Test 3

Verdict: ACCEPTED

input
1
9

correct output
1

user output
1

Test 4

Verdict:

input
100
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
0

user output
1

Test 5

Verdict:

input
100
0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 ...

correct output
25

user output
26

Test 6

Verdict:

input
100
2 1 2 1 2 0 0 0 1 1 2 2 1 2 2 ...

correct output
41

user output
42

Test 7

Verdict:

input
100
36 5 10 37 94 59 20 31 64 2 58...

correct output
99

user output
100

Test 8

Verdict: ACCEPTED

input
100
228768416 32415139 952687252 6...

correct output
100

user output
100

Test 9

Verdict:

input
100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
0

user output
1

Test 10

Verdict:

input
100000
1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 ...

correct output
24965

user output
24966

Test 11

Verdict:

input
100000
2 1 2 2 2 2 2 1 1 0 1 1 0 1 1 ...

correct output
38968

user output
38969

Test 12

Verdict:

input
100000
4 4 5 4 4 5 0 2 2 1 4 4 1 0 5 ...

correct output
59156

user output
59157

Test 13

Verdict:

input
100000
18 5 6 16 8 10 1 7 4 15 5 9 19...

correct output
82598

user output
82599

Test 14

Verdict:

input
100000
33 37 37 86 42 38 18 10 77 57 ...

correct output
94897

user output
94898