oj.uz

Submission #956869

# Submission time Handle Problem Language Result Execution time Memory
956869 2024-04-02T15:11:08 Z HoriaHaivas Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2642 ms 155000 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;
    st=apos-1;
    while (st>0 && state[st]==1)
    {
        st--;
    }
    st++;
    dr=apos+1;
    while (dr<n+1 && state[dr]==1)
    {
        dr++;
    }
    dr--;
    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]);
            state[pos[i]]=1-state[pos[i]];
        }
    }
    for (i=1; i<=n+1; i++)
    {
        vals[i].push_back(0);
        sort(vals[i].begin(),vals[i].end());
        aib[i].resize(vals[i].size());
        state[i]=initialstate[i];
    }
    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:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (; newy<=aib[x].size(); newy+=newy&(-newy))
      |                ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:126:19: warning: unused variable 'j' [-Wunused-variable]
  126 |     long long q,i,j,cnt;
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 5 ms 19136 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 496 ms 46996 KB Output is correct
2 Correct 648 ms 56016 KB Output is correct
3 Correct 1020 ms 67320 KB Output is correct
4 Correct 1422 ms 103156 KB Output is correct
5 Correct 1215 ms 88340 KB Output is correct
6 Correct 1634 ms 116276 KB Output is correct
7 Correct 194 ms 45392 KB Output is correct
8 Correct 189 ms 46848 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19292 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 2612 ms 147004 KB Output is correct
6 Correct 1930 ms 118792 KB Output is correct
7 Correct 1140 ms 82420 KB Output is correct
8 Correct 223 ms 40780 KB Output is correct
9 Correct 67 ms 20212 KB Output is correct
10 Correct 73 ms 20052 KB Output is correct
11 Correct 72 ms 20404 KB Output is correct
12 Correct 190 ms 39504 KB Output is correct
13 Correct 172 ms 40840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 6 ms 19292 KB Output is correct
5 Correct 233 ms 46356 KB Output is correct
6 Correct 885 ms 79656 KB Output is correct
7 Correct 1634 ms 116636 KB Output is correct
8 Correct 2642 ms 155000 KB Output is correct
9 Correct 864 ms 74412 KB Output is correct
10 Correct 862 ms 77004 KB Output is correct
11 Correct 854 ms 74856 KB Output is correct
12 Correct 844 ms 76188 KB Output is correct
13 Correct 888 ms 75436 KB Output is correct
14 Correct 817 ms 76008 KB Output is correct
15 Correct 199 ms 45436 KB Output is correct
16 Correct 207 ms 46676 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 5 ms 19136 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 496 ms 46996 KB Output is correct
9 Correct 648 ms 56016 KB Output is correct
10 Correct 1020 ms 67320 KB Output is correct
11 Correct 1422 ms 103156 KB Output is correct
12 Correct 1215 ms 88340 KB Output is correct
13 Correct 1634 ms 116276 KB Output is correct
14 Correct 194 ms 45392 KB Output is correct
15 Correct 189 ms 46848 KB Output is correct
16 Correct 6 ms 19292 KB Output is correct
17 Correct 7 ms 19292 KB Output is correct
18 Correct 6 ms 19036 KB Output is correct
19 Correct 4 ms 19036 KB Output is correct
20 Correct 2612 ms 147004 KB Output is correct
21 Correct 1930 ms 118792 KB Output is correct
22 Correct 1140 ms 82420 KB Output is correct
23 Correct 223 ms 40780 KB Output is correct
24 Correct 67 ms 20212 KB Output is correct
25 Correct 73 ms 20052 KB Output is correct
26 Correct 72 ms 20404 KB Output is correct
27 Correct 190 ms 39504 KB Output is correct
28 Correct 172 ms 40840 KB Output is correct
29 Correct 4 ms 19032 KB Output is correct
30 Correct 5 ms 19036 KB Output is correct
31 Correct 5 ms 19292 KB Output is correct
32 Correct 6 ms 19292 KB Output is correct
33 Correct 233 ms 46356 KB Output is correct
34 Correct 885 ms 79656 KB Output is correct
35 Correct 1634 ms 116636 KB Output is correct
36 Correct 2642 ms 155000 KB Output is correct
37 Correct 864 ms 74412 KB Output is correct
38 Correct 862 ms 77004 KB Output is correct
39 Correct 854 ms 74856 KB Output is correct
40 Correct 844 ms 76188 KB Output is correct
41 Correct 888 ms 75436 KB Output is correct
42 Correct 817 ms 76008 KB Output is correct
43 Correct 199 ms 45436 KB Output is correct
44 Correct 207 ms 46676 KB Output is correct
45 Correct 121 ms 34552 KB Output is correct
46 Correct 283 ms 39664 KB Output is correct
47 Correct 778 ms 63984 KB Output is correct
48 Correct 1366 ms 103036 KB Output is correct
49 Correct 87 ms 23584 KB Output is correct
50 Correct 75 ms 23536 KB Output is correct
51 Correct 73 ms 23800 KB Output is correct
52 Correct 89 ms 23884 KB Output is correct
53 Correct 74 ms 24056 KB Output is correct
54 Correct 72 ms 23892 KB Output is correct