oj.uz

Submission #564213

# Submission time Handle Problem Language Result Execution time Memory
564213 2022-05-18T18:12:36 Z groshi Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1146 ms 47988 KB 
#include<iostream>
#include<map>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
struct wi{
    int x,y;
}*w;
map<int,int> mapka;
int drzewo[3000000],drzewo2[3000000];
int zap[3000000];
int pot=1;
vector<pair<int,int> > Q,Q2;
int zapp(int x,int y)
{
    x+=pot;
    y+=pot;
    int wynik=0;
    wynik=drzewo[x];
    wynik=max(wynik,drzewo[y]);
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik=max(wynik,drzewo[x+1]);
        if(y%2==1)
            wynik=max(wynik,drzewo[y-1]);
        x/=2;
        y/=2;
    }
    return wynik;
}
void dodaj(int x)
{
    x+=pot;
    drzewo2[x]=1;
    x/=2;
    while(x>=1)
    {
        drzewo2[x]=drzewo2[x*2]+drzewo2[x*2+1];
        x/=2;
    }
}
int zapp2(int x,int y)
{
    x+=pot;
    y+=pot;
    int wynik=0;
    wynik=drzewo2[x];
    if(x!=y)
        wynik+=drzewo2[y];
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik+=drzewo2[x+1];
        if(y%2==1)
            wynik+=drzewo2[y-1];
        x/=2;
        y/=2;
    }
    return wynik;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,x,y;
    cin>>n>>k;
    w=new wi[n+3];
    while(pot<=3*max(n,k))
        pot*=2;
    pot--;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        w[i].x=x;
        w[i].y=y;
        mapka[x]=1;
        mapka[y]=1;
        Q.push_back({max(x,y),i});
    }
    sort(Q.begin(),Q.end());
    for(int i=1;i<=k;i++)
    {
        cin>>x;
        mapka[x]=1;
        zap[i]=x;
        Q2.push_back({x,i});
    }
    sort(Q2.begin(),Q2.end());
    int kiedy=1;
    for(auto it=mapka.begin();it!=mapka.end();it++)
    {
        mapka[it->first]=kiedy;
        kiedy++;
    }
    for(int i=1;i<=k;i++)
    {
        auto it=mapka.find(zap[i]);
        drzewo[it->second+pot]=i;
    }
    for(int i=pot;i>=1;i--)
        drzewo[i]=max(drzewo[i*2+1],drzewo[i*2]);
    int wskaz=Q2.size()-1;
    long long wypisz=0;
    for(int i=Q.size()-1;i>=0;i--)
    {
        int maxx=Q[i].first;
        int co=Q[i].second;
        int gosciu=zapp(mapka[min(w[co].x,w[co].y)],mapka[max(w[co].x,w[co].y)]-1);
        //cout<<maxx<<" "<<co<<" "<<gosciu<<" ";
        while(wskaz>=0 && Q2[wskaz].first>=maxx)
        {
            dodaj(Q2[wskaz].second);
            wskaz--;
        }
        int ile=zapp2(gosciu+1,pot+1);
        //cout<<ile<<"\n";
        if(gosciu==0)
        {
            if(ile%2==0)
                wypisz+=w[co].x;
            else wypisz+=w[co].y;
            continue;
        }
        if(ile%2==0)
            wypisz+=maxx;
        else{
            if(w[co].x==maxx)
                wypisz+=w[co].y;
            else wypisz+=w[co].x;
        }
        //cout<<wypisz<<"\n";
    }
    cout<<wypisz;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 552 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 544 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 552 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 544 KB Output is correct
14 Correct 22 ms 2644 KB Output is correct
15 Correct 47 ms 4956 KB Output is correct
16 Correct 77 ms 7408 KB Output is correct
17 Correct 141 ms 9564 KB Output is correct
18 Correct 110 ms 9556 KB Output is correct
19 Correct 101 ms 9548 KB Output is correct
20 Correct 112 ms 9448 KB Output is correct
21 Correct 118 ms 9452 KB Output is correct
22 Correct 68 ms 7144 KB Output is correct
23 Correct 59 ms 6096 KB Output is correct
24 Correct 51 ms 5300 KB Output is correct
25 Correct 79 ms 7848 KB Output is correct
26 Correct 70 ms 6960 KB Output is correct
27 Correct 70 ms 7508 KB Output is correct
28 Correct 65 ms 7484 KB Output is correct
29 Correct 80 ms 8536 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 552 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 544 KB Output is correct
14 Correct 22 ms 2644 KB Output is correct
15 Correct 47 ms 4956 KB Output is correct
16 Correct 77 ms 7408 KB Output is correct
17 Correct 141 ms 9564 KB Output is correct
18 Correct 110 ms 9556 KB Output is correct
19 Correct 101 ms 9548 KB Output is correct
20 Correct 112 ms 9448 KB Output is correct
21 Correct 118 ms 9452 KB Output is correct
22 Correct 68 ms 7144 KB Output is correct
23 Correct 59 ms 6096 KB Output is correct
24 Correct 51 ms 5300 KB Output is correct
25 Correct 79 ms 7848 KB Output is correct
26 Correct 70 ms 6960 KB Output is correct
27 Correct 70 ms 7508 KB Output is correct
28 Correct 65 ms 7484 KB Output is correct
29 Correct 80 ms 8536 KB Output is correct
30 Correct 301 ms 21916 KB Output is correct
31 Correct 444 ms 27268 KB Output is correct
32 Correct 676 ms 34108 KB Output is correct
33 Correct 1146 ms 47900 KB Output is correct
34 Correct 243 ms 20408 KB Output is correct
35 Correct 1108 ms 47988 KB Output is correct
36 Correct 1089 ms 47940 KB Output is correct
37 Correct 1110 ms 47864 KB Output is correct
38 Correct 1010 ms 47784 KB Output is correct
39 Correct 1046 ms 47888 KB Output is correct
40 Correct 949 ms 47624 KB Output is correct
41 Correct 905 ms 47812 KB Output is correct
42 Correct 987 ms 47880 KB Output is correct
43 Correct 509 ms 44988 KB Output is correct
44 Correct 534 ms 45304 KB Output is correct
45 Correct 576 ms 46168 KB Output is correct
46 Correct 510 ms 30976 KB Output is correct
47 Correct 427 ms 25556 KB Output is correct
48 Correct 570 ms 37760 KB Output is correct
49 Correct 590 ms 37808 KB Output is correct