oj.uz

Submission #728058

# Submission time Handle Problem Language Result Execution time Memory
728058 2023-04-21T21:56:39 Z Seb Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 718 ms 81448 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 2e5 + 5;
const ll INF = 1e16;

#define f first
#define s second

struct st{
ll ini,fin;
st *l,*r;
vector <ll> v;
st (ll INI, ll FIN) {
    ini = INI;
    fin = FIN;
    l = nullptr;
    r = nullptr;
}
};

pair <ll,ll> num[MAXN];
ll op[MAXN], act[MAXN], ans;

void setup(st *nodo) {
    if (nodo->ini==nodo->fin) {
        nodo->v.push_back(op[nodo->ini]);
        return;
    }
    nodo->l = new st(nodo->ini,(nodo->ini+nodo->fin)/2);
    nodo->r = new st((nodo->ini+nodo->fin)/2+1,nodo->fin);
    setup(nodo->l);
    setup(nodo->r);
    int i=0,j=0;
    while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
        if (nodo->l->v[i] > nodo->r->v[j]) {
            nodo->v.push_back(nodo->r->v[j]);
            j++;
        }
        else {
            nodo->v.push_back(nodo->l->v[i]);
            i++;
        }
    }
    while (i<nodo->l->v.size()) {
        nodo->v.push_back(nodo->l->v[i]);
        i++;
    }
    while (j<nodo->r->v.size()) {
        nodo->v.push_back(nodo->r->v[j]);
        j++;
    }
    return;
}

ll bin(st *nodo, ll ini, ll fin, ll x) {
    if (ini==fin) return ini;
    if (nodo->v[(ini+fin)/2] > x) return bin(nodo,ini,(ini+fin)/2,x);
    else return bin(nodo,(ini+fin)/2+1,fin,x);
}

ll query(st *nodo, ll L, ll R, ll x) {
    if (L>nodo->fin || nodo->ini>R) return 0;
    if (L<=nodo->ini && nodo->fin<=R) return bin(nodo,0,nodo->v.size(),x);
    return query(nodo->l,L,R,x) + query(nodo->r,L,R,x);
}

ll cami(st *nodo, ll x1, ll x2) {
    if (nodo->ini==nodo->fin) return nodo->ini;
    if (bin(nodo->r,0,nodo->r->v.size(),x2) - bin(nodo->r,0,nodo->r->v.size(),x1-1) > 0) return cami(nodo->r,x1,x2);
    else return cami(nodo->l,x1,x2);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,k,in;
cin>>n>>k;
for (int i=0;i<n;i++) {
    cin>>num[i].f>>num[i].s;
    act[i] = num[i].f;
    if (num[i].f>num[i].s) swap(num[i].f,num[i].s);
}
for (int i=0;i<k;i++) cin>>op[i];
st *nodo = new st(0,k-1);
setup(nodo);
for (int i=0;i<n;i++) {
    if (bin(nodo,0,nodo->v.size(),num[i].s-1) - bin(nodo,0,nodo->v.size(),num[i].f-1) > 0) {
        act[i] = num[i].s;
        in = cami(nodo,num[i].f,num[i].s-1) + 1;
    }
    else in = 0;
    if ((k-in-query(nodo,in,k-1,num[i].f-1))%2==1) {
        if (act[i]==num[i].f) act[i] = num[i].s;
        else act[i] = num[i].f;
    }
    ans += act[i];
}
cout<<ans;
return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void setup(st*)':
fortune_telling2.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
      |            ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:38:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
      |                                   ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (i<nodo->l->v.size()) {
      |            ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while (j<nodo->r->v.size()) {
      |            ~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 20 ms 4288 KB Output is correct
15 Correct 46 ms 8284 KB Output is correct
16 Correct 74 ms 11216 KB Output is correct
17 Correct 101 ms 16696 KB Output is correct
18 Correct 106 ms 16712 KB Output is correct
19 Correct 104 ms 16784 KB Output is correct
20 Correct 107 ms 16716 KB Output is correct
21 Correct 85 ms 16660 KB Output is correct
22 Correct 54 ms 16264 KB Output is correct
23 Correct 55 ms 16312 KB Output is correct
24 Correct 62 ms 16216 KB Output is correct
25 Correct 53 ms 16276 KB Output is correct
26 Correct 83 ms 16436 KB Output is correct
27 Correct 115 ms 16776 KB Output is correct
28 Correct 80 ms 16744 KB Output is correct
29 Correct 75 ms 16780 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 20 ms 4288 KB Output is correct
15 Correct 46 ms 8284 KB Output is correct
16 Correct 74 ms 11216 KB Output is correct
17 Correct 101 ms 16696 KB Output is correct
18 Correct 106 ms 16712 KB Output is correct
19 Correct 104 ms 16784 KB Output is correct
20 Correct 107 ms 16716 KB Output is correct
21 Correct 85 ms 16660 KB Output is correct
22 Correct 54 ms 16264 KB Output is correct
23 Correct 55 ms 16312 KB Output is correct
24 Correct 62 ms 16216 KB Output is correct
25 Correct 53 ms 16276 KB Output is correct
26 Correct 83 ms 16436 KB Output is correct
27 Correct 115 ms 16776 KB Output is correct
28 Correct 80 ms 16744 KB Output is correct
29 Correct 75 ms 16780 KB Output is correct
30 Correct 138 ms 73236 KB Output is correct
31 Correct 248 ms 74944 KB Output is correct
32 Correct 401 ms 77060 KB Output is correct
33 Correct 674 ms 81256 KB Output is correct
34 Correct 113 ms 72768 KB Output is correct
35 Correct 718 ms 81356 KB Output is correct
36 Correct 683 ms 81296 KB Output is correct
37 Correct 679 ms 81328 KB Output is correct
38 Correct 656 ms 81296 KB Output is correct
39 Correct 701 ms 81272 KB Output is correct
40 Correct 517 ms 81088 KB Output is correct
41 Correct 664 ms 81344 KB Output is correct
42 Correct 684 ms 81280 KB Output is correct
43 Correct 317 ms 80724 KB Output is correct
44 Correct 295 ms 80624 KB Output is correct
45 Correct 278 ms 80656 KB Output is correct
46 Correct 321 ms 79496 KB Output is correct
47 Correct 374 ms 79352 KB Output is correct
48 Correct 583 ms 81348 KB Output is correct
49 Correct 475 ms 81448 KB Output is correct