oj.uz

Submission #956937

# Submission time Handle Problem Language Result Execution time Memory
956937 2024-04-02T17:34:32 Z HoriaHaivas Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2923 ms 149804 KB 
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct event
{
    int x;
    int y;
    int moment;
};

int mom,n;
bool state[300005];
bool initialstate[300005];
bool type[300005];
int l[300005];
int r[300005];
int pos[300005];
int altaib[300005];
vector<event> updates;
vector<int> vals[300005];
vector<int> aib[300005];

void altupdate(int index, int delta)
{
    while (index<=n)
    {
        altaib[index]+=delta;
        index+=index&(-index);
    }
}

int altquery(int index)
{
    int ans;
    ans=0;
    while (index>0)
    {
        ans+=altaib[index];
        index-=index&(-index);
    }
    return ans;
}

void setupdate(int x, int y)
{
    for (; x<=n; x+=x&(-x))
    {
        vals[x].push_back(y);
    }
}

void updatinho(int apos)
{
    int st,dr,pas;
    if (state[apos]==1)
    {
        st=apos;
        pas=(1<<17);
        while (pas)
        {
            if (st-pas>0 && altquery(apos)-altquery(st-pas-1)==apos-(st-pas)+1)
                st-=pas;
            pas=pas/2;
        }
        dr=apos;
        pas=(1<<17);
        while (pas)
        {
            if (dr+pas<=n && altquery(dr+pas)-altquery(apos-1)==dr+pas-apos+1)
                dr+=pas;
            pas=pas/2;
        }
    }
    else
    {
        st=apos;
        pas=(1<<17);
        while (pas)
        {
            if (st-pas>0 && altquery(apos)-altquery(st-pas-1)==apos-(st-pas))
                st-=pas;
            pas=pas/2;
        }
        dr=apos;
        pas=(1<<17);
        while (pas)
        {
            if (dr+pas<=n && altquery(dr+pas)-altquery(apos-1)==dr+pas-apos)
                dr+=pas;
            pas=pas/2;
        }
    }
    setupdate(st,apos);
    updates.push_back({st,apos,mom});
    setupdate(apos+1,apos);
    updates.push_back({apos+1,apos,mom});
    setupdate(st,dr+1);
    updates.push_back({st,dr+1,mom});
    setupdate(apos+1,dr+1);
    updates.push_back({apos+1,dr+1,mom});
}

int indice(int x, int y)
{
    return upper_bound(vals[x].begin(),vals[x].end(),y)-vals[x].begin()-1;
}

void update(int x, int y, int delta)
{
    int newy;
    for (; x<=n; x+=x&(-x))
    {
        newy=indice(x,y);
        for (; newy<=aib[x].size(); newy+=newy&(-newy))
        {
            aib[x][newy]+=delta;
        }
    }
}

int query(int x, int y)
{
    int ans,newy;
    ans=0;
    for (; x>0; x-=x&(-x))
    {
        newy=indice(x,y);
        for (; newy>0; newy-=newy&(-newy))
        {
            ans+=aib[x][newy];
        }
    }
    return ans;
}

signed main()
{
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long q,i,j,cnt;
    char ch;
    string s;
    cin >> n >> q;
    for (i=1; i<=n; i++)
    {
        cin >> ch;
        if (ch=='0')
            state[i]=0;
        else
            state[i]=1;
        if (state[i]==1)
            altupdate(i,1);
        initialstate[i]=state[i];
    }
    for (i=1; i<=q; i++)
    {
        cin >> s;
        if (s=="query")
            type[i]=1;
        else
            type[i]=0;
        if (type[i]==1)
        {
            cin >> l[i] >> r[i];
        }
        else
        {
            cin >> pos[i];
            mom=i;
            updatinho(pos[i]);
            if (state[pos[i]]==1)
                altupdate(pos[i],-1);
            else
                altupdate(pos[i],1);
            state[pos[i]]=1-state[pos[i]];
        }
    }
    for (i=1; i<=n+1; i++)
    {
        altaib[i]=0;
        vals[i].push_back(0);
        sort(vals[i].begin(),vals[i].end());
        aib[i].resize(vals[i].size());
        state[i]=initialstate[i];
    }
    for (i=1;i<=n;i++)
    {
         if (state[i]==1)
            altupdate(i,1);
    }
    cnt=0;
    for (i=1; i<=q; i++)
    {
        if (type[i]==1)
        {
            if (altquery(r[i]-1)-altquery(l[i]-1)==(r[i]-l[i]))
                cout << i+query(l[i],r[i]-1) << "\n";
            else
                cout << query(l[i],r[i]-1) << "\n";
        }
        else
        {
            if (state[pos[i]]==1)
            {
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                altupdate(pos[i],-1);
            }
            else
            {
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                altupdate(pos[i],1);
            }
            state[pos[i]]=1-state[pos[i]];
        }
    }
}

Compilation message

street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (; newy<=aib[x].size(); newy+=newy&(-newy))
      |                ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:152:19: warning: unused variable 'j' [-Wunused-variable]
  152 |     long long q,i,j,cnt;
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 5 ms 19112 KB Output is correct
5 Correct 5 ms 19288 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 47524 KB Output is correct
2 Correct 626 ms 51176 KB Output is correct
3 Correct 981 ms 62140 KB Output is correct
4 Correct 1493 ms 98276 KB Output is correct
5 Correct 1290 ms 83700 KB Output is correct
6 Correct 1750 ms 112652 KB Output is correct
7 Correct 177 ms 39380 KB Output is correct
8 Correct 218 ms 40700 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19288 KB Output is correct
2 Correct 6 ms 19292 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 2923 ms 147820 KB Output is correct
6 Correct 2064 ms 119652 KB Output is correct
7 Correct 1243 ms 82536 KB Output is correct
8 Correct 183 ms 40864 KB Output is correct
9 Correct 66 ms 19984 KB Output is correct
10 Correct 72 ms 20136 KB Output is correct
11 Correct 68 ms 20284 KB Output is correct
12 Correct 182 ms 39580 KB Output is correct
13 Correct 179 ms 40764 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 5 ms 19252 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 7 ms 19292 KB Output is correct
5 Correct 234 ms 40504 KB Output is correct
6 Correct 911 ms 75284 KB Output is correct
7 Correct 1718 ms 110256 KB Output is correct
8 Correct 2792 ms 149804 KB Output is correct
9 Correct 908 ms 73964 KB Output is correct
10 Correct 815 ms 73276 KB Output is correct
11 Correct 889 ms 72684 KB Output is correct
12 Correct 829 ms 73212 KB Output is correct
13 Correct 873 ms 71576 KB Output is correct
14 Correct 855 ms 72648 KB Output is correct
15 Correct 165 ms 39276 KB Output is correct
16 Correct 179 ms 40904 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 5 ms 19112 KB Output is correct
5 Correct 5 ms 19288 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 492 ms 47524 KB Output is correct
9 Correct 626 ms 51176 KB Output is correct
10 Correct 981 ms 62140 KB Output is correct
11 Correct 1493 ms 98276 KB Output is correct
12 Correct 1290 ms 83700 KB Output is correct
13 Correct 1750 ms 112652 KB Output is correct
14 Correct 177 ms 39380 KB Output is correct
15 Correct 218 ms 40700 KB Output is correct
16 Correct 7 ms 19288 KB Output is correct
17 Correct 6 ms 19292 KB Output is correct
18 Correct 7 ms 19036 KB Output is correct
19 Correct 4 ms 19036 KB Output is correct
20 Correct 2923 ms 147820 KB Output is correct
21 Correct 2064 ms 119652 KB Output is correct
22 Correct 1243 ms 82536 KB Output is correct
23 Correct 183 ms 40864 KB Output is correct
24 Correct 66 ms 19984 KB Output is correct
25 Correct 72 ms 20136 KB Output is correct
26 Correct 68 ms 20284 KB Output is correct
27 Correct 182 ms 39580 KB Output is correct
28 Correct 179 ms 40764 KB Output is correct
29 Correct 4 ms 19036 KB Output is correct
30 Correct 5 ms 19252 KB Output is correct
31 Correct 5 ms 19292 KB Output is correct
32 Correct 7 ms 19292 KB Output is correct
33 Correct 234 ms 40504 KB Output is correct
34 Correct 911 ms 75284 KB Output is correct
35 Correct 1718 ms 110256 KB Output is correct
36 Correct 2792 ms 149804 KB Output is correct
37 Correct 908 ms 73964 KB Output is correct
38 Correct 815 ms 73276 KB Output is correct
39 Correct 889 ms 72684 KB Output is correct
40 Correct 829 ms 73212 KB Output is correct
41 Correct 873 ms 71576 KB Output is correct
42 Correct 855 ms 72648 KB Output is correct
43 Correct 165 ms 39276 KB Output is correct
44 Correct 179 ms 40904 KB Output is correct
45 Correct 125 ms 33376 KB Output is correct
46 Correct 282 ms 36448 KB Output is correct
47 Correct 778 ms 60512 KB Output is correct
48 Correct 1470 ms 96608 KB Output is correct
49 Correct 71 ms 20048 KB Output is correct
50 Correct 68 ms 20084 KB Output is correct
51 Correct 72 ms 20000 KB Output is correct
52 Correct 70 ms 20052 KB Output is correct
53 Correct 69 ms 20136 KB Output is correct
54 Correct 70 ms 20048 KB Output is correct