oj.uz

Submission #465885

# Submission time Handle Problem Language Result Execution time Memory
465885 2021-08-17T07:01:01 Z alextodoran Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2779 ms 218608 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

typedef long long ll;

const int N_MAX = 300000;
const int Q_MAX = 300000;

const int BUFFER_SIZE = 200000;

char buffer[BUFFER_SIZE];
int bpos = BUFFER_SIZE - 1;

char read_char ()
{
    bpos++;
    if(bpos == BUFFER_SIZE)
    {
        fread(buffer, sizeof(char), BUFFER_SIZE, stdin);
        bpos = 0;
    }
    return buffer[bpos];
}

bool isDigit[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int read_int ()
{
    char c;
    while(!isDigit[c = read_char()]);
    int ans = 0;
    do
    {
        ans = ans * 10 + c - '0';
    }
    while(isDigit[c = read_char()]);
    return ans;
}

char bufferOut[BUFFER_SIZE];
int opos = -1;

void print_buffer ()
{
    fwrite(bufferOut, sizeof(char), opos + 1, stdout);
}

void print_char (char c)
{
    if(opos == BUFFER_SIZE - 1)
    {
        print_buffer();
        opos = -1;
    }
    opos++;
    bufferOut[opos] = c;
}

void print_int (int a)
{
    if(a == 0)
    {
        print_char('0');
        return;
    }
    int a1 = a, p10 = 1;
    while(a1)
    {
        p10 *= 10;
        a1 /= 10;
    }
    p10 /= 10;
    while(p10)
    {
        print_char(a / p10 % 10 + '0');
        a %= p10;
        p10 /= 10;
    }
}

int n, q;

bool light[N_MAX + 2];
bool old[N_MAX + 2];

int L[Q_MAX + 2];
int R[Q_MAX + 2];
bool full[Q_MAX + 2];

struct Query
{
    bool type;
    int pos;
    int l, r;
};

Query queries[Q_MAX + 2];

struct SGTNode
{
    int len;
    int pref;
    int suff;
};

SGTNode join (const SGTNode &u, const SGTNode &v)
{
    return SGTNode
    {
        u.len + v.len,
        (u.pref == u.len ? u.len + v.pref : u.pref),
        (v.suff == v.len ? v.len + u.suff : v.suff)
    };
}

SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r)
{
    if(l == r)
    {
        SGT[node] = SGTNode{1, light[l], light[l]};
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    build(lSon, l, mid);
    build(rSon, mid + 1, r);

    SGT[node] = join(SGT[lSon], SGT[rSon]);
}
void build ()
{
    build(1, 1, n);
}

void update (int node, int l, int r, int upos)
{
    if(l == r)
    {
        SGT[node].pref = 1 - SGT[node].pref;
        SGT[node].suff = 1 - SGT[node].suff;
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    if(upos <= mid)
        update(lSon, l, mid, upos);
    else
        update(rSon, mid + 1, r, upos);

    SGT[node] = join(SGT[lSon], SGT[rSon]);
}
void update (int upos)
{
    update(1, 1, n, upos);
}

SGTNode query (int node, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return SGT[node];

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    if(ql <= mid && mid + 1 <= qr)
        return join(query(lSon, l, mid, ql, qr), query(rSon, mid + 1, r, ql, qr));
    else if(ql <= mid)
        return query(lSon, l, mid, ql, qr);
    else
        return query(rSon, mid + 1, r, ql, qr);
}
SGTNode query (int ql, int qr)
{
    if(ql > qr)
        return SGTNode{0, 0, 0};
    return query(1, 1, n, ql, qr);
}

vector <int> BITpos[(N_MAX + 1) + 2];

vector <int> BIT[(N_MAX + 1) + 2];

void BITupdateSim (int x, int y)
{
    for(int i = x; i <= y; i += i & -i)
        for(int j = y; j >= i; j -= j & -j)
            BITpos[i].push_back(j);
}

void BITquerySim (int x, int y)
{
    for(int i = x; i >= 1; i -= i & -i)
        for(int j = y; j <= n + 1; j += j & -j)
            BITpos[i].push_back(j);
}

void compress (int i)
{
    sort(BITpos[i].begin(), BITpos[i].end());
    BITpos[i].resize(unique(BITpos[i].begin(), BITpos[i].end()) - BITpos[i].begin());
    BIT[i].resize((int) BITpos[i].size() + 1);
}
int getPos (int i, int y)
{
    int l = 0, r = (int) BITpos[i].size();
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(BITpos[i][mid] < y)
            l = mid + 1;
        else
            r = mid;
    }
    return l + 1;
}

void BITupdate (int x, int y, int uval)
{
    for(int i = x; i <= y; i += i & -i)
        for(int j = getPos(i, y); j >= 1; j -= j & -j)
            BIT[i][j] += uval;
}

int BITquery (int x, int y)
{
    int answer = 0;
    for(int i = x; i >= 1; i -= i & -i)
        for(int j = getPos(i, y); j <= (int) BITpos[i].size(); j += j & -j)
            answer += BIT[i][j];
    return answer;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    n = read_int();
    q = read_int();

    for(int i = 1; i <= n; i++)
        light[i] = old[i] = (read_char() == '1');
    read_char();

    build();

    for(int i = 1; i <= n; i++)
        if(light[i] == true)
        {
            int j = i;
            while(j < n && light[j + 1] == true)
                j++;

            BITupdateSim(i, j + 1);

            i = j;
        }

    for(int qi = 1; qi <= q; qi++)
    {
        if(read_char() == 't')
        {
            queries[qi].type = 0;

            int upos = read_int();

            queries[qi].pos = upos;

            int lLen = query(1, upos - 1).suff;
            int rLen = query(upos + 1, n).pref;

            L[qi] = upos - lLen;
            R[qi] = upos + 1 + rLen;

            int l = L[qi];
            int r = R[qi];

            if(light[upos] == true)
            {
                BITupdateSim(l, r);
                BITupdateSim(l, upos);
                BITupdateSim(upos + 1, r);
            }

            light[upos] = !light[upos];
            update(upos);

            if(light[upos] == true)
            {
                BITupdateSim(l, r);
                BITupdateSim(l, upos);
                BITupdateSim(upos + 1, r);
            }

        }
        else
        {
            queries[qi].type = 1;

            int l = read_int();
            int r = read_int();

            queries[qi].l = l;
            queries[qi].r = r;

            BITquerySim(l, r);

            full[qi] = (query(l, r - 1).pref == r - l);
        }
    }

    for(int i = 1; i <= n + 1; i++)
        compress(i);

    /// ======================================================================================

    for(int i = 1; i <= n; i++)
        light[i] = old[i];

    for(int i = 1; i <= n; i++)
        if(light[i] == true)
        {
            int j = i;
            while(j < n && light[j + 1] == true)
                j++;

            BITupdate(i, j + 1, + q);

            i = j;
        }

    for(int qi = 1; qi <= q; qi++)
    {
        if(queries[qi].type == 0)
        {
            int upos = queries[qi].pos;

            int l = L[qi];
            int r = R[qi];

            if(light[upos] == true)
            {
                BITupdate(l, r, - (q - qi));
                BITupdate(l, upos, + (q - qi));
                BITupdate(upos + 1, r, + (q - qi));
            }

            light[upos] = !light[upos];

            if(light[upos] == true)
            {
                BITupdate(l, r, + (q - qi));
                BITupdate(l, upos, - (q - qi));
                BITupdate(upos + 1, r, - (q - qi));
            }

        }
        else
        {
            int l = queries[qi].l;
            int r = queries[qi].r;

            int answer = BITquery(l, r);

            if(full[qi] == true)
                answer -= (q - qi);

            print_int(answer);
            print_char('\n');
        }
    }

    print_buffer();

    return 0;
}

Compilation message

street_lamps.cpp: In function 'int read_int()':
street_lamps.cpp:59:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |     while(!isDigit[c = read_char()]);
      |                    ~~^~~~~~~~~~~~~
street_lamps.cpp:65:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |     while(isDigit[c = read_char()]);
      |                   ~~^~~~~~~~~~~~~
street_lamps.cpp: In function 'char read_char()':
street_lamps.cpp:32:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         fread(buffer, sizeof(char), BUFFER_SIZE, stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14380 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14472 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 36256 KB Output is correct
2 Correct 283 ms 41648 KB Output is correct
3 Correct 502 ms 57640 KB Output is correct
4 Correct 1634 ms 129860 KB Output is correct
5 Correct 1911 ms 148056 KB Output is correct
6 Correct 1398 ms 115400 KB Output is correct
7 Correct 2248 ms 184544 KB Output is correct
8 Correct 2252 ms 186296 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 10 ms 14668 KB Output is correct
3 Correct 10 ms 14644 KB Output is correct
4 Correct 10 ms 14668 KB Output is correct
5 Correct 851 ms 71668 KB Output is correct
6 Correct 1451 ms 119688 KB Output is correct
7 Correct 2114 ms 165592 KB Output is correct
8 Correct 2776 ms 212732 KB Output is correct
9 Correct 165 ms 31020 KB Output is correct
10 Correct 169 ms 34624 KB Output is correct
11 Correct 211 ms 38428 KB Output is correct
12 Correct 2696 ms 217588 KB Output is correct
13 Correct 2733 ms 218524 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14796 KB Output is correct
2 Correct 10 ms 14668 KB Output is correct
3 Correct 10 ms 14668 KB Output is correct
4 Correct 10 ms 14616 KB Output is correct
5 Correct 2777 ms 218608 KB Output is correct
6 Correct 2152 ms 175204 KB Output is correct
7 Correct 1508 ms 130604 KB Output is correct
8 Correct 766 ms 67884 KB Output is correct
9 Correct 293 ms 40872 KB Output is correct
10 Correct 214 ms 35848 KB Output is correct
11 Correct 293 ms 40744 KB Output is correct
12 Correct 213 ms 35524 KB Output is correct
13 Correct 289 ms 40616 KB Output is correct
14 Correct 215 ms 35468 KB Output is correct
15 Correct 2771 ms 217392 KB Output is correct
16 Correct 2779 ms 218212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14380 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14472 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 203 ms 36256 KB Output is correct
9 Correct 283 ms 41648 KB Output is correct
10 Correct 502 ms 57640 KB Output is correct
11 Correct 1634 ms 129860 KB Output is correct
12 Correct 1911 ms 148056 KB Output is correct
13 Correct 1398 ms 115400 KB Output is correct
14 Correct 2248 ms 184544 KB Output is correct
15 Correct 2252 ms 186296 KB Output is correct
16 Correct 10 ms 14540 KB Output is correct
17 Correct 10 ms 14668 KB Output is correct
18 Correct 10 ms 14644 KB Output is correct
19 Correct 10 ms 14668 KB Output is correct
20 Correct 851 ms 71668 KB Output is correct
21 Correct 1451 ms 119688 KB Output is correct
22 Correct 2114 ms 165592 KB Output is correct
23 Correct 2776 ms 212732 KB Output is correct
24 Correct 165 ms 31020 KB Output is correct
25 Correct 169 ms 34624 KB Output is correct
26 Correct 211 ms 38428 KB Output is correct
27 Correct 2696 ms 217588 KB Output is correct
28 Correct 2733 ms 218524 KB Output is correct
29 Correct 11 ms 14796 KB Output is correct
30 Correct 10 ms 14668 KB Output is correct
31 Correct 10 ms 14668 KB Output is correct
32 Correct 10 ms 14616 KB Output is correct
33 Correct 2777 ms 218608 KB Output is correct
34 Correct 2152 ms 175204 KB Output is correct
35 Correct 1508 ms 130604 KB Output is correct
36 Correct 766 ms 67884 KB Output is correct
37 Correct 293 ms 40872 KB Output is correct
38 Correct 214 ms 35848 KB Output is correct
39 Correct 293 ms 40744 KB Output is correct
40 Correct 213 ms 35524 KB Output is correct
41 Correct 289 ms 40616 KB Output is correct
42 Correct 215 ms 35468 KB Output is correct
43 Correct 2771 ms 217392 KB Output is correct
44 Correct 2779 ms 218212 KB Output is correct
45 Correct 88 ms 26588 KB Output is correct
46 Correct 167 ms 30740 KB Output is correct
47 Correct 949 ms 82008 KB Output is correct
48 Correct 1750 ms 147548 KB Output is correct
49 Correct 203 ms 38228 KB Output is correct
50 Correct 187 ms 36336 KB Output is correct
51 Correct 242 ms 41088 KB Output is correct
52 Correct 338 ms 47520 KB Output is correct
53 Correct 333 ms 47656 KB Output is correct
54 Correct 338 ms 47524 KB Output is correct