oj.uz

Submission #466168

# Submission time Handle Problem Language Result Execution time Memory
466168 2021-08-18T09:01:33 Z Tenis0206 Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 471 ms 31884 KB 
#include <bits/stdc++.h>

using namespace std;
int n,k,a[200005],b[200005],t[200005];
vector<int> v;
int rez[200005],cnt[200005];
int auxa[200005],auxb[200005];
vector<pair<int,int>> Q[200005];
class arbore_de_intervale
{
    int ai[2500005];
public:
    void update(int poz, int val, int nod, int a, int b)
    {
        if(a==b)
        {
            ai[nod] = max(ai[nod],val);
            return;
        }
        int mij = (a+b)>>1;
        if(poz<=mij)
        {
            update(poz,val,nod*2,a,mij);
        }
        else
        {
            update(poz,val,nod*2+1,mij+1,b);
        }
        ai[nod] = max(ai[nod*2],ai[nod*2+1]);
    }
    int query(int qa, int qb, int nod, int a, int b)
    {
        if(qa<=a && qb>=b)
        {
            return ai[nod];
        }
        int mij = (a+b)>>1;
        int rez1 = 0, rez2 = 0;
        if(qa<=mij)
        {
            rez1 = query(qa,qb,nod*2,a,mij);
        }
        if(qb>mij)
        {
            rez2 = query(qa,qb,nod*2+1,mij+1,b);
        }
        return max(rez1,rez2);
    }
} ai;
class arbore_indexat_binar
{
    int aib[600005];
private:
    int ub(int x)
    {
        return (x&(-x));
    }
public:
    void update(int poz, int val)
    {
        for(int i=poz; i<=v.size(); i+=ub(i))
        {
            aib[i]+=val;
        }
    }
    int query(int qa, int qb)
    {
        int rez = 0;
        for(int i=qb; i>=1; i-=ub(i))
        {
            rez+=aib[i];
        }
        for(int i=qa-1; i>=1; i-=ub(i))
        {
            rez-=aib[i];
        }
        return rez;
    }
} aib;
int get_poz(int val)
{
    int st = 1;
    int dr = v.size();
    int poz = 0;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij-1]>=val)
        {
            poz = mij;
            dr = mij-1;
        }
        else
        {
            st = mij+1;
        }
    }
    return poz;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i]>>b[i];
        auxa[i] = a[i];
        auxb[i] = b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    for(int i=1; i<=k; i++)
    {
        cin>>t[i];
        v.push_back(t[i]);
    }
    sort(v.begin(),v.end());
    for(int i=1; i<=n; i++)
    {
        a[i] = get_poz(a[i]);
        b[i] = get_poz(b[i]);
    }
    for(int i=1; i<=k; i++)
    {
        t[i] = get_poz(t[i]);
        ai.update(t[i],i,1,1,v.size());
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i]==b[i])
        {
            continue;
        }
        int poz = ai.query(min(a[i],b[i]),max(a[i],b[i])-1,1,1,v.size());
        if(poz)
        {
            rez[i] = max(a[i],b[i]);
        }
        else
        {
            rez[i] = a[i];
        }
        Q[poz+1].push_back({max(a[i],b[i]),i});
    }
    for(int i=k; i>=1; i--)
    {
        aib.update(t[i],+1);
        for(auto it : Q[i])
        {
            cnt[it.second] = aib.query(it.first,v.size());
        }
    }
    long long sum = 0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]==b[i])
        {
            sum+=auxa[i];
            continue;
        }
        if(cnt[i]%2==1)
        {
            if(rez[i]==a[i])
            {
                rez[i] = b[i];
            }
            else
            {
                rez[i] = a[i];
            }
        }
        if(rez[i]==a[i])
        {
            sum+=auxa[i];
        }
        else
        {
            sum+=auxb[i];
        }
    }
    cout<<sum<<'\n';
    return 0;
}

Compilation message

fortune_telling2.cpp: In member function 'void arbore_indexat_binar::update(int, int)':
fortune_telling2.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int i=poz; i<=v.size(); i+=ub(i))
      |                        ~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5052 KB Output is correct
3 Correct 4 ms 5184 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5184 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 5 ms 5196 KB Output is correct
13 Correct 4 ms 5196 KB Output is correct
14 Correct 17 ms 6192 KB Output is correct
15 Correct 34 ms 7428 KB Output is correct
16 Correct 51 ms 8784 KB Output is correct
17 Correct 70 ms 9656 KB Output is correct
18 Correct 69 ms 9660 KB Output is correct
19 Correct 71 ms 9716 KB Output is correct
20 Correct 89 ms 9788 KB Output is correct
21 Correct 67 ms 10056 KB Output is correct
22 Correct 54 ms 9188 KB Output is correct
23 Correct 54 ms 9140 KB Output is correct
24 Correct 53 ms 9176 KB Output is correct
25 Correct 54 ms 9228 KB Output is correct
26 Correct 52 ms 9004 KB Output is correct
27 Correct 62 ms 9788 KB Output is correct
28 Correct 55 ms 9276 KB Output is correct
29 Correct 63 ms 9696 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5052 KB Output is correct
3 Correct 4 ms 5184 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5184 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 5 ms 5196 KB Output is correct
13 Correct 4 ms 5196 KB Output is correct
14 Correct 17 ms 6192 KB Output is correct
15 Correct 34 ms 7428 KB Output is correct
16 Correct 51 ms 8784 KB Output is correct
17 Correct 70 ms 9656 KB Output is correct
18 Correct 69 ms 9660 KB Output is correct
19 Correct 71 ms 9716 KB Output is correct
20 Correct 89 ms 9788 KB Output is correct
21 Correct 67 ms 10056 KB Output is correct
22 Correct 54 ms 9188 KB Output is correct
23 Correct 54 ms 9140 KB Output is correct
24 Correct 53 ms 9176 KB Output is correct
25 Correct 54 ms 9228 KB Output is correct
26 Correct 52 ms 9004 KB Output is correct
27 Correct 62 ms 9788 KB Output is correct
28 Correct 55 ms 9276 KB Output is correct
29 Correct 63 ms 9696 KB Output is correct
30 Correct 163 ms 12068 KB Output is correct
31 Correct 187 ms 16952 KB Output is correct
32 Correct 269 ms 20436 KB Output is correct
33 Correct 418 ms 31648 KB Output is correct
34 Correct 131 ms 11508 KB Output is correct
35 Correct 406 ms 31708 KB Output is correct
36 Correct 471 ms 31512 KB Output is correct
37 Correct 406 ms 31260 KB Output is correct
38 Correct 403 ms 31536 KB Output is correct
39 Correct 405 ms 31292 KB Output is correct
40 Correct 440 ms 31884 KB Output is correct
41 Correct 414 ms 31456 KB Output is correct
42 Correct 415 ms 31152 KB Output is correct
43 Correct 278 ms 26440 KB Output is correct
44 Correct 281 ms 27004 KB Output is correct
45 Correct 295 ms 28456 KB Output is correct
46 Correct 296 ms 29232 KB Output is correct
47 Correct 291 ms 29308 KB Output is correct
48 Correct 315 ms 28328 KB Output is correct
49 Correct 299 ms 28432 KB Output is correct