oj.uz

Submission #466498

# Submission time Handle Problem Language Result Execution time Memory
466498 2021-08-19T13:17:23 Z stefantaga Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1398 ms 81796 KB 
#include <bits/stdc++.h>

using namespace std;
long long n,m,i,nr[600005],st,dr,sol,mij,solfin[600005],ceau[600005],arb[2400005];
struct wow
{
    long long x,y;
} v[600005];
map <int,int> m2;
pair <int,int> sal[600005];
void update (long long st,long long dr,long long nod,long long poz,long long val)
{
    if (st==dr)
    {
        arb[nod]=val;
        return;
    }
    long long mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
long long query(long long st,long long dr,long long nod,long long ua,long long ub)
{
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    long long r1=0,r2=0,mij=(st+dr)/2;
    if (ua<=mij)
    {
        r1=query(st,mij,2*nod,ua,ub);
    }
    if (mij<ub)
    {
        r2=query(mij+1,dr,2*nod+1,ua,ub);
    }
    return max(r1,r2);
}
long long ub(long long x)
{
    return x&(-x);
}
long long aib[400005],nr2;
void upd(long long x,long long val)
{
    long long i;
    for (i=x; i<=nr2; i+=ub(i))
    {
        aib[i]+=val;
    }
}
long long suma(long long poz)
{
    long long i,sumi=0;
    for (i=poz; i>=1; i-=ub(i))
    {
        sumi=sumi+aib[i];
    }
    return sumi;
}
long long inv[600005];
vector <int> ev[600005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>n>>m;
    for (i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y;
        m2[v[i].x]=1;
        m2[v[i].y]=1;
    }
    for (i=1; i<=m; i++)
    {
        cin>>nr[i];
        m2[nr[i]]=1;
    }
    nr2=0;
    for (auto ind: m2)
    {
        nr2++;
        inv[nr2]=ind.first;
        m2[ind.first]=nr2;
    }
    for (i=1; i<=n; i++)
    {
        v[i].x=m2[v[i].x];
        v[i].y=m2[v[i].y];
    }
    for (i=1; i<=m; i++)
    {
        nr[i]=m2[nr[i]];
    }
    for (i=1; i<=m; i++)
    {
        update(1,nr2,1,nr[i],i);
    }
    for (i=1; i<=n; i++)
    {
        st=min(v[i].x,v[i].y);
        dr=max(v[i].x,v[i].y);
        if (st<dr)
        {
            ceau[i]=query(1,nr2,1,st,dr-1);
        }
    }
    for (i=1; i<=4*nr2; i++)
    {
        arb[i]=0;
    }
    for (i=1; i<=n; i++)
    {
        ev[ceau[i]].push_back(i);
    }
    long long sum=0;
    for (i=m; i>=1; i--)
    {
        for (long long j=0; j<ev[i].size(); j++)
        {
            long long nod=ev[i][j];
            long long dr=max(v[nod].x,v[nod].y);
            long long valu=suma(nr2)-suma(dr-1);
            if (valu%2==0)
            {
                sum=sum+max(inv[v[nod].x],inv[v[nod].y]);
            }
            else
            {
                sum=sum+min(inv[v[nod].x],inv[v[nod].y]);
            }
        }
        if (i!=0)
        {
            upd(nr[i],1);
        }
    }
    for (long long j=0; j<ev[0].size(); j++)
    {
        long long nod=ev[0][j];
        long long dr=max(v[nod].x,v[nod].y);
        long long valu=suma(nr2)-suma(dr-1);
        if (v[nod].x==min(v[nod].x,v[nod].y))
        {
            if (valu%2==1)
            {
                sum=sum+max(inv[v[nod].x],inv[v[nod].y]);
            }
            else
            {
                sum=sum+min(inv[v[nod].x],inv[v[nod].y]);
            }
        }
        else
        {
            if (valu%2==0)
            {
                sum=sum+max(inv[v[nod].x],inv[v[nod].y]);
            }
            else
            {
                sum=sum+min(inv[v[nod].x],inv[v[nod].y]);
            }
        }
    }
    cout<<sum;
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:130:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (long long j=0; j<ev[i].size(); j++)
      |                             ~^~~~~~~~~~~~~
fortune_telling2.cpp:149:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (long long j=0; j<ev[0].size(); j++)
      |                         ~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14540 KB Output is correct
2 Correct 9 ms 14584 KB Output is correct
3 Correct 10 ms 14668 KB Output is correct
4 Correct 10 ms 14668 KB Output is correct
5 Correct 11 ms 14756 KB Output is correct
6 Correct 10 ms 14768 KB Output is correct
7 Correct 10 ms 14728 KB Output is correct
8 Correct 11 ms 14652 KB Output is correct
9 Correct 10 ms 14668 KB Output is correct
10 Correct 11 ms 14540 KB Output is correct
11 Correct 10 ms 14628 KB Output is correct
12 Correct 10 ms 14644 KB Output is correct
13 Correct 10 ms 14604 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14540 KB Output is correct
2 Correct 9 ms 14584 KB Output is correct
3 Correct 10 ms 14668 KB Output is correct
4 Correct 10 ms 14668 KB Output is correct
5 Correct 11 ms 14756 KB Output is correct
6 Correct 10 ms 14768 KB Output is correct
7 Correct 10 ms 14728 KB Output is correct
8 Correct 11 ms 14652 KB Output is correct
9 Correct 10 ms 14668 KB Output is correct
10 Correct 11 ms 14540 KB Output is correct
11 Correct 10 ms 14628 KB Output is correct
12 Correct 10 ms 14644 KB Output is correct
13 Correct 10 ms 14604 KB Output is correct
14 Correct 35 ms 17612 KB Output is correct
15 Correct 69 ms 20804 KB Output is correct
16 Correct 100 ms 23968 KB Output is correct
17 Correct 146 ms 27092 KB Output is correct
18 Correct 143 ms 27212 KB Output is correct
19 Correct 170 ms 27336 KB Output is correct
20 Correct 145 ms 27180 KB Output is correct
21 Correct 139 ms 27200 KB Output is correct
22 Correct 114 ms 23384 KB Output is correct
23 Correct 93 ms 21580 KB Output is correct
24 Correct 81 ms 20056 KB Output is correct
25 Correct 106 ms 24564 KB Output is correct
26 Correct 91 ms 22552 KB Output is correct
27 Correct 109 ms 23364 KB Output is correct
28 Correct 97 ms 23428 KB Output is correct
29 Correct 121 ms 25324 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14540 KB Output is correct
2 Correct 9 ms 14584 KB Output is correct
3 Correct 10 ms 14668 KB Output is correct
4 Correct 10 ms 14668 KB Output is correct
5 Correct 11 ms 14756 KB Output is correct
6 Correct 10 ms 14768 KB Output is correct
7 Correct 10 ms 14728 KB Output is correct
8 Correct 11 ms 14652 KB Output is correct
9 Correct 10 ms 14668 KB Output is correct
10 Correct 11 ms 14540 KB Output is correct
11 Correct 10 ms 14628 KB Output is correct
12 Correct 10 ms 14644 KB Output is correct
13 Correct 10 ms 14604 KB Output is correct
14 Correct 35 ms 17612 KB Output is correct
15 Correct 69 ms 20804 KB Output is correct
16 Correct 100 ms 23968 KB Output is correct
17 Correct 146 ms 27092 KB Output is correct
18 Correct 143 ms 27212 KB Output is correct
19 Correct 170 ms 27336 KB Output is correct
20 Correct 145 ms 27180 KB Output is correct
21 Correct 139 ms 27200 KB Output is correct
22 Correct 114 ms 23384 KB Output is correct
23 Correct 93 ms 21580 KB Output is correct
24 Correct 81 ms 20056 KB Output is correct
25 Correct 106 ms 24564 KB Output is correct
26 Correct 91 ms 22552 KB Output is correct
27 Correct 109 ms 23364 KB Output is correct
28 Correct 97 ms 23428 KB Output is correct
29 Correct 121 ms 25324 KB Output is correct
30 Correct 323 ms 36884 KB Output is correct
31 Correct 522 ms 48524 KB Output is correct
32 Correct 783 ms 60152 KB Output is correct
33 Correct 1344 ms 81544 KB Output is correct
34 Correct 287 ms 36804 KB Output is correct
35 Correct 1259 ms 81612 KB Output is correct
36 Correct 1398 ms 81496 KB Output is correct
37 Correct 1292 ms 81496 KB Output is correct
38 Correct 1257 ms 81792 KB Output is correct
39 Correct 1246 ms 81796 KB Output is correct
40 Correct 1116 ms 81548 KB Output is correct
41 Correct 1200 ms 81744 KB Output is correct
42 Correct 1300 ms 81624 KB Output is correct
43 Correct 684 ms 79292 KB Output is correct
44 Correct 672 ms 79552 KB Output is correct
45 Correct 668 ms 80280 KB Output is correct
46 Correct 611 ms 53448 KB Output is correct
47 Correct 498 ms 44100 KB Output is correct
48 Correct 729 ms 62916 KB Output is correct
49 Correct 689 ms 62904 KB Output is correct