oj.uz

Submission #251389

# Submission time Handle Problem Language Result Execution time Memory
251389 2020-07-21T05:26:35 Z jeqcho Street Lamps (APIO19_street_lamps) C++17
20 / 100
 273 ms 12904 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

int const N=101;
int ans[N][N];
int n,q;
string S;

vector<int> seg;
int arr_sz;
int init_value = 1e9+3;

int build(int idex, int lx, int rx)
{
    if(lx==rx-1)return seg[idex];
    // Operation specific
    seg[idex] = max(build(2*idex+1, lx,(lx+rx)/2 ), build(2*idex+2, (lx+rx)/2,rx));
    return seg[idex];
}

void update(int idex, int val)
{
    idex += arr_sz-1;
    seg[idex] = val;
    --idex;
    while(idex>=0)
    {
        idex /= 2;
        // Operation specific
        seg[idex] = max(seg[2*idex+1], seg[2*idex+2]);
        --idex;
    }
}

int maxq(int idex, int lq, int rq, int lx, int rx)
{
    if(lx>=lq&&rx<=rq)return seg[idex];
    else if(lx>=rq||rx<=lq) return -init_value;
    // Operation specific
    int lef = maxq(2*idex+1,lq,rq, lx,(lx+rx)/2 );
    int rig = maxq(2*idex+2,lq,rq, (lx+rx)/2,rx);
    return max(lef, rig);
}

int query(int a,int b, int t)
{
    int ans = maxq(0,a,b,0,arr_sz);
    if(ans==init_value)return 0;
    return t-ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;

    int p2 = ceil(log2((long double)n));
    arr_sz = 1<<p2;
    int tree_sz = 2*arr_sz;
    seg.rsz(tree_sz);
    fill(all(seg),init_value);
    cin>>S;
    F0R(i,n)
    {
        if(S[i]=='1')seg[arr_sz-1 + i]=0;
    }
    build(0,0,arr_sz);

    string typ;
    int i,a,b;
    int t=1;
    while(q--)
    {
        cin>>typ;
        if(typ=="toggle")
        {
            cin>>i;
            --i;
            update(i,t);
        }
        else
        {
            cin>>a>>b;
            --a; --b;
            cout<<query(a,b,t)<<'\n';
        }
        ++t;
    }
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 1016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 105 ms 9228 KB Output is correct
6 Correct 142 ms 9868 KB Output is correct
7 Correct 184 ms 10508 KB Output is correct
8 Correct 273 ms 12812 KB Output is correct
9 Correct 97 ms 3960 KB Output is correct
10 Correct 105 ms 4472 KB Output is correct
11 Correct 115 ms 4700 KB Output is correct
12 Correct 242 ms 11404 KB Output is correct
13 Correct 248 ms 12904 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -