oj.uz

Submission #82799

# Submission time Handle Problem Language Result Execution time Memory
82799 2018-11-01T18:39:50 Z Bodo171 Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 1676 ms 79596 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[10*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 5240 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 8 ms 5372 KB Output is correct
4 Correct 8 ms 5400 KB Output is correct
5 Correct 8 ms 5508 KB Output is correct
6 Correct 8 ms 5616 KB Output is correct
7 Correct 8 ms 5708 KB Output is correct
8 Correct 8 ms 5956 KB Output is correct
9 Correct 8 ms 5956 KB Output is correct
10 Correct 8 ms 5956 KB Output is correct
11 Correct 8 ms 5956 KB Output is correct
12 Correct 7 ms 5956 KB Output is correct
13 Correct 9 ms 5956 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 8 ms 5372 KB Output is correct
4 Correct 8 ms 5400 KB Output is correct
5 Correct 8 ms 5508 KB Output is correct
6 Correct 8 ms 5616 KB Output is correct
7 Correct 8 ms 5708 KB Output is correct
8 Correct 8 ms 5956 KB Output is correct
9 Correct 8 ms 5956 KB Output is correct
10 Correct 8 ms 5956 KB Output is correct
11 Correct 8 ms 5956 KB Output is correct
12 Correct 7 ms 5956 KB Output is correct
13 Correct 9 ms 5956 KB Output is correct
14 Correct 38 ms 8060 KB Output is correct
15 Correct 90 ms 10856 KB Output is correct
16 Correct 130 ms 13968 KB Output is correct
17 Correct 186 ms 16968 KB Output is correct
18 Correct 190 ms 18092 KB Output is correct
19 Correct 201 ms 19288 KB Output is correct
20 Correct 185 ms 20484 KB Output is correct
21 Correct 190 ms 21676 KB Output is correct
22 Correct 128 ms 21676 KB Output is correct
23 Correct 118 ms 21676 KB Output is correct
24 Correct 107 ms 21676 KB Output is correct
25 Correct 133 ms 22928 KB Output is correct
26 Correct 125 ms 22928 KB Output is correct
27 Correct 149 ms 24408 KB Output is correct
28 Correct 130 ms 25416 KB Output is correct
29 Correct 173 ms 27896 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 8 ms 5372 KB Output is correct
4 Correct 8 ms 5400 KB Output is correct
5 Correct 8 ms 5508 KB Output is correct
6 Correct 8 ms 5616 KB Output is correct
7 Correct 8 ms 5708 KB Output is correct
8 Correct 8 ms 5956 KB Output is correct
9 Correct 8 ms 5956 KB Output is correct
10 Correct 8 ms 5956 KB Output is correct
11 Correct 8 ms 5956 KB Output is correct
12 Correct 7 ms 5956 KB Output is correct
13 Correct 9 ms 5956 KB Output is correct
14 Correct 38 ms 8060 KB Output is correct
15 Correct 90 ms 10856 KB Output is correct
16 Correct 130 ms 13968 KB Output is correct
17 Correct 186 ms 16968 KB Output is correct
18 Correct 190 ms 18092 KB Output is correct
19 Correct 201 ms 19288 KB Output is correct
20 Correct 185 ms 20484 KB Output is correct
21 Correct 190 ms 21676 KB Output is correct
22 Correct 128 ms 21676 KB Output is correct
23 Correct 118 ms 21676 KB Output is correct
24 Correct 107 ms 21676 KB Output is correct
25 Correct 133 ms 22928 KB Output is correct
26 Correct 125 ms 22928 KB Output is correct
27 Correct 149 ms 24408 KB Output is correct
28 Correct 130 ms 25416 KB Output is correct
29 Correct 173 ms 27896 KB Output is correct
30 Correct 534 ms 37776 KB Output is correct
31 Correct 702 ms 47812 KB Output is correct
32 Correct 1035 ms 57840 KB Output is correct
33 Incorrect 1676 ms 79596 KB Output isn't correct
34 Halted 0 ms 0 KB -