oj.uz

Submission #82800

# Submission time Handle Problem Language Result Execution time Memory
82800 2018-11-01T18:41:24 Z Bodo171 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1624 ms 119800 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <map>
using namespace std;
const int nmax=200005;
vector<int> all,qry[nmax];
map<int,int> norm;
int aib[3*nmax],arb[12*nmax];
int a[nmax],b[nmax],val[nmax];
int n,k,st,dr,poz,value,ans,i,lim,ind;
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod]=value;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r)
{
    if(st<=l&&r<=dr)
    {
        ans=max(ans,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m);
    if(m<dr) query(2*nod+1,m+1,r);
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void upd(int poz)
{
    for(int idx=poz;idx<=lim;idx+=lbit(idx))
        aib[idx]^=1;
}
int qr(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret^=aib[idx];
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        all.push_back(a[i]);
        all.push_back(b[i]);
    }
    for(i=1;i<=k;i++)
    {
        cin>>val[i];
        all.push_back(val[i]);
    }
    sort(all.begin(),all.end());
    unique(all.begin(),all.end());
    for(int i=0;i<all.size();i++)
        norm[all[i]]=i+1;
    lim=all.size();
    for(i=1;i<=k;i++)
    {
        poz=norm[val[i]];value=i;
        update(1,1,lim);
    }
    for(i=1;i<=n;i++)
    {
        ans=0;
        st=norm[min(a[i],b[i])];dr=norm[max(a[i],b[i])]-1;
        if(st>dr)
            continue;
        query(1,1,lim);
        if(ans!=0&&a[i]<b[i])
            swap(a[i],b[i]);
        qry[ans+1].push_back(i);
    }
    for(i=k+1;i>=1;i--)
    {
        if(i<=k) upd(norm[val[i]]);
        for(int j=0;j<qry[i].size();j++)
        {
            ind=qry[i][j];
            poz=norm[min(a[ind],b[ind])];
            if(qr(lim)^qr(poz-1))
                swap(a[ind],b[ind]);
        }
    }
    long long sum=0;
    for(i=1;i<=n;i++)
        sum+=1LL*a[i];
    cout<<sum;
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<all.size();i++)
                 ~^~~~~~~~~~~
fortune_telling2.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<qry[i].size();j++)
                     ~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 8 ms 5320 KB Output is correct
5 Correct 9 ms 5320 KB Output is correct
6 Correct 9 ms 5320 KB Output is correct
7 Correct 8 ms 5320 KB Output is correct
8 Correct 8 ms 5320 KB Output is correct
9 Correct 8 ms 5480 KB Output is correct
10 Correct 7 ms 5480 KB Output is correct
11 Correct 9 ms 5512 KB Output is correct
12 Correct 9 ms 5512 KB Output is correct
13 Correct 7 ms 5512 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 8 ms 5320 KB Output is correct
5 Correct 9 ms 5320 KB Output is correct
6 Correct 9 ms 5320 KB Output is correct
7 Correct 8 ms 5320 KB Output is correct
8 Correct 8 ms 5320 KB Output is correct
9 Correct 8 ms 5480 KB Output is correct
10 Correct 7 ms 5480 KB Output is correct
11 Correct 9 ms 5512 KB Output is correct
12 Correct 9 ms 5512 KB Output is correct
13 Correct 7 ms 5512 KB Output is correct
14 Correct 39 ms 7324 KB Output is correct
15 Correct 87 ms 9372 KB Output is correct
16 Correct 141 ms 11672 KB Output is correct
17 Correct 213 ms 13604 KB Output is correct
18 Correct 200 ms 13616 KB Output is correct
19 Correct 204 ms 13616 KB Output is correct
20 Correct 208 ms 13732 KB Output is correct
21 Correct 202 ms 13732 KB Output is correct
22 Correct 135 ms 13732 KB Output is correct
23 Correct 117 ms 13732 KB Output is correct
24 Correct 114 ms 13732 KB Output is correct
25 Correct 138 ms 13732 KB Output is correct
26 Correct 126 ms 13732 KB Output is correct
27 Correct 147 ms 13732 KB Output is correct
28 Correct 135 ms 13732 KB Output is correct
29 Correct 179 ms 13732 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 8 ms 5320 KB Output is correct
5 Correct 9 ms 5320 KB Output is correct
6 Correct 9 ms 5320 KB Output is correct
7 Correct 8 ms 5320 KB Output is correct
8 Correct 8 ms 5320 KB Output is correct
9 Correct 8 ms 5480 KB Output is correct
10 Correct 7 ms 5480 KB Output is correct
11 Correct 9 ms 5512 KB Output is correct
12 Correct 9 ms 5512 KB Output is correct
13 Correct 7 ms 5512 KB Output is correct
14 Correct 39 ms 7324 KB Output is correct
15 Correct 87 ms 9372 KB Output is correct
16 Correct 141 ms 11672 KB Output is correct
17 Correct 213 ms 13604 KB Output is correct
18 Correct 200 ms 13616 KB Output is correct
19 Correct 204 ms 13616 KB Output is correct
20 Correct 208 ms 13732 KB Output is correct
21 Correct 202 ms 13732 KB Output is correct
22 Correct 135 ms 13732 KB Output is correct
23 Correct 117 ms 13732 KB Output is correct
24 Correct 114 ms 13732 KB Output is correct
25 Correct 138 ms 13732 KB Output is correct
26 Correct 126 ms 13732 KB Output is correct
27 Correct 147 ms 13732 KB Output is correct
28 Correct 135 ms 13732 KB Output is correct
29 Correct 179 ms 13732 KB Output is correct
30 Correct 502 ms 20436 KB Output is correct
31 Correct 718 ms 27344 KB Output is correct
32 Correct 992 ms 33616 KB Output is correct
33 Correct 1536 ms 50296 KB Output is correct
34 Correct 446 ms 50296 KB Output is correct
35 Correct 1539 ms 57984 KB Output is correct
36 Correct 1520 ms 63652 KB Output is correct
37 Correct 1624 ms 69456 KB Output is correct
38 Correct 1576 ms 75204 KB Output is correct
39 Correct 1476 ms 80832 KB Output is correct
40 Correct 1468 ms 87192 KB Output is correct
41 Correct 1508 ms 92320 KB Output is correct
42 Correct 1506 ms 98384 KB Output is correct
43 Correct 924 ms 99256 KB Output is correct
44 Correct 962 ms 104832 KB Output is correct
45 Correct 994 ms 111288 KB Output is correct
46 Correct 900 ms 111288 KB Output is correct
47 Correct 815 ms 111288 KB Output is correct
48 Correct 993 ms 114356 KB Output is correct
49 Correct 972 ms 119800 KB Output is correct