oj.uz

Submission #362077

# Submission time Handle Problem Language Result Execution time Memory
362077 2021-02-01T16:57:09 Z denkendoemeer Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 869 ms 55288 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[200005],b[200005],v[200005],v2[200005];
vector<int>aint[800005];
void init(int nod,int st,int dr)
{
    int i;
    for(i=st;i<=dr;i++)
        aint[nod].push_back(v[i]);
    sort(aint[nod].begin(),aint[nod].end());
    if (st!=dr){
        int mij=(st+dr)/2;
        init(nod*2,st,mij);
        init(nod*2+1,mij+1,dr);
    }
}
int ind(vector<int>&aux,int nr)
{
    return aux.size()-(lower_bound(aux.begin(),aux.end(),nr)-aux.begin());
}
int query(int nod,int st,int dr,int l,int r)
{
    if (st==dr){
        if (l<=aint[nod][0] && aint[nod][0]<r)
            return st;
        else
            return st-1;
    }
    else{
        int mij=(st+dr)/2;
        if (ind(aint[nod*2+1],l)-ind(aint[nod*2+1],r))
            return query(nod*2+1,mij+1,dr,l,r);
        else
            return query(nod*2,st,mij,l,r);
    }
}
int query2(int nod,int st,int dr,int l,int r,int nr)
{
    if (st==l && dr==r)
        return ind(aint[nod],nr);
    int mij=(st+dr)/2;
    if (r<=mij)
        return query2(nod*2,st,mij,l,r,nr);
    else
        if (l>mij)
            return query2(nod*2+1,mij+1,dr,l,r,nr);
        else
            return query2(nod*2,st,mij,l,mij,nr)+query2(nod*2+1,mij+1,dr,mij+1,r,nr);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,k,i;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if (a[i]>b[i]){
            swap(a[i],b[i]);
            v2[i]=1;
        }
    }
    for(i=1;i<=k;i++)
        scanf("%d",&v[i]);
    init(1,1,k);
    ll ans=0;
    for(i=0;i<n;i++){
        int aux=query(1,1,k,a[i],b[i]);
        if (aux)
            v2[i]=1;
        if (aux<k)
            v2[i]+=query2(1,1,k,aux+1,k,a[i]);
        if (v2[i]&1)
            ans+=b[i];
        else
            ans+=a[i];
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d%d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19180 KB Output is correct
2 Correct 15 ms 19308 KB Output is correct
3 Correct 15 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 15 ms 19308 KB Output is correct
6 Correct 15 ms 19308 KB Output is correct
7 Correct 15 ms 19308 KB Output is correct
8 Correct 14 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 15 ms 19180 KB Output is correct
11 Correct 17 ms 19308 KB Output is correct
12 Correct 15 ms 19308 KB Output is correct
13 Correct 15 ms 19308 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19180 KB Output is correct
2 Correct 15 ms 19308 KB Output is correct
3 Correct 15 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 15 ms 19308 KB Output is correct
6 Correct 15 ms 19308 KB Output is correct
7 Correct 15 ms 19308 KB Output is correct
8 Correct 14 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 15 ms 19180 KB Output is correct
11 Correct 17 ms 19308 KB Output is correct
12 Correct 15 ms 19308 KB Output is correct
13 Correct 15 ms 19308 KB Output is correct
14 Correct 39 ms 20972 KB Output is correct
15 Correct 68 ms 22764 KB Output is correct
16 Correct 105 ms 24044 KB Output is correct
17 Correct 135 ms 26472 KB Output is correct
18 Correct 141 ms 26600 KB Output is correct
19 Correct 133 ms 26472 KB Output is correct
20 Correct 145 ms 26600 KB Output is correct
21 Correct 133 ms 26472 KB Output is correct
22 Correct 92 ms 25960 KB Output is correct
23 Correct 98 ms 26136 KB Output is correct
24 Correct 96 ms 26088 KB Output is correct
25 Correct 87 ms 25960 KB Output is correct
26 Correct 112 ms 26216 KB Output is correct
27 Correct 146 ms 26472 KB Output is correct
28 Correct 114 ms 26600 KB Output is correct
29 Correct 147 ms 26472 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19180 KB Output is correct
2 Correct 15 ms 19308 KB Output is correct
3 Correct 15 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 15 ms 19308 KB Output is correct
6 Correct 15 ms 19308 KB Output is correct
7 Correct 15 ms 19308 KB Output is correct
8 Correct 14 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 15 ms 19180 KB Output is correct
11 Correct 17 ms 19308 KB Output is correct
12 Correct 15 ms 19308 KB Output is correct
13 Correct 15 ms 19308 KB Output is correct
14 Correct 39 ms 20972 KB Output is correct
15 Correct 68 ms 22764 KB Output is correct
16 Correct 105 ms 24044 KB Output is correct
17 Correct 135 ms 26472 KB Output is correct
18 Correct 141 ms 26600 KB Output is correct
19 Correct 133 ms 26472 KB Output is correct
20 Correct 145 ms 26600 KB Output is correct
21 Correct 133 ms 26472 KB Output is correct
22 Correct 92 ms 25960 KB Output is correct
23 Correct 98 ms 26136 KB Output is correct
24 Correct 96 ms 26088 KB Output is correct
25 Correct 87 ms 25960 KB Output is correct
26 Correct 112 ms 26216 KB Output is correct
27 Correct 146 ms 26472 KB Output is correct
28 Correct 114 ms 26600 KB Output is correct
29 Correct 147 ms 26472 KB Output is correct
30 Correct 322 ms 49272 KB Output is correct
31 Correct 433 ms 50564 KB Output is correct
32 Correct 560 ms 52212 KB Output is correct
33 Correct 831 ms 55136 KB Output is correct
34 Correct 291 ms 48864 KB Output is correct
35 Correct 827 ms 55288 KB Output is correct
36 Correct 842 ms 55136 KB Output is correct
37 Correct 826 ms 55264 KB Output is correct
38 Correct 830 ms 55184 KB Output is correct
39 Correct 853 ms 55136 KB Output is correct
40 Correct 692 ms 54896 KB Output is correct
41 Correct 869 ms 55184 KB Output is correct
42 Correct 853 ms 55264 KB Output is correct
43 Correct 492 ms 54496 KB Output is correct
44 Correct 492 ms 54488 KB Output is correct
45 Correct 495 ms 54624 KB Output is correct
46 Correct 510 ms 53216 KB Output is correct
47 Correct 540 ms 53044 KB Output is correct
48 Correct 732 ms 55264 KB Output is correct
49 Correct 663 ms 55236 KB Output is correct