oj.uz

Submission #465879

# Submission time Handle Problem Language Result Execution time Memory
465879 2021-08-17T06:31:44 Z alextodoran Street Lamps (APIO19_street_lamps) C++17
40 / 100
 4597 ms 524292 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];

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);
}

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

void BITupdate (int x, int y, int uval)
{
    for(int i = x; i <= n + 1; i += i & -i)
        for(int j = y; j >= i; 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 = y; j <= n + 1; 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] = (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++;

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

            i = j;
        }

    for(int qi = 1; qi <= q; qi++)
    {
        if(read_char() == 't')
        {
            int upos = read_int();

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

            int l = upos - lLen;
            int r = upos + 1 + rLen;

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

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

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

        }
        else
        {
            int l = read_int();
            int r = read_int();

            int answer = BITquery(l, r);
            if(query(l, r - 1).pref == r - l)
                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 12 ms 16844 KB Output is correct
2 Correct 10 ms 16716 KB Output is correct
3 Correct 10 ms 16716 KB Output is correct
4 Correct 11 ms 16844 KB Output is correct
5 Correct 10 ms 16768 KB Output is correct
6 Correct 10 ms 16764 KB Output is correct
7 Correct 10 ms 16716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21320 KB Output is correct
2 Correct 139 ms 21060 KB Output is correct
3 Correct 273 ms 24548 KB Output is correct
4 Correct 1955 ms 181288 KB Output is correct
5 Correct 2259 ms 202596 KB Output is correct
6 Correct 1624 ms 171240 KB Output is correct
7 Correct 2374 ms 202640 KB Output is correct
8 Correct 2360 ms 204096 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16972 KB Output is correct
2 Correct 13 ms 17192 KB Output is correct
3 Correct 12 ms 17272 KB Output is correct
4 Correct 12 ms 17412 KB Output is correct
5 Correct 911 ms 112044 KB Output is correct
6 Correct 2805 ms 283028 KB Output is correct
7 Correct 4597 ms 435060 KB Output is correct
8 Runtime error 4451 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17356 KB Output is correct
2 Correct 13 ms 17340 KB Output is correct
3 Correct 12 ms 17160 KB Output is correct
4 Correct 12 ms 16896 KB Output is correct
5 Runtime error 4420 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16844 KB Output is correct
2 Correct 10 ms 16716 KB Output is correct
3 Correct 10 ms 16716 KB Output is correct
4 Correct 11 ms 16844 KB Output is correct
5 Correct 10 ms 16768 KB Output is correct
6 Correct 10 ms 16764 KB Output is correct
7 Correct 10 ms 16716 KB Output is correct
8 Correct 107 ms 21320 KB Output is correct
9 Correct 139 ms 21060 KB Output is correct
10 Correct 273 ms 24548 KB Output is correct
11 Correct 1955 ms 181288 KB Output is correct
12 Correct 2259 ms 202596 KB Output is correct
13 Correct 1624 ms 171240 KB Output is correct
14 Correct 2374 ms 202640 KB Output is correct
15 Correct 2360 ms 204096 KB Output is correct
16 Correct 12 ms 16972 KB Output is correct
17 Correct 13 ms 17192 KB Output is correct
18 Correct 12 ms 17272 KB Output is correct
19 Correct 12 ms 17412 KB Output is correct
20 Correct 911 ms 112044 KB Output is correct
21 Correct 2805 ms 283028 KB Output is correct
22 Correct 4597 ms 435060 KB Output is correct
23 Runtime error 4451 ms 524292 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -