oj.uz

Submission #979056

# Submission time Handle Problem Language Result Execution time Memory
979056 2024-05-10T07:16:52 Z Kenjikrab Street Lamps (APIO19_street_lamps) C++14
80 / 100
 5000 ms 44868 KB 
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef pair<llt, int> pli;
typedef complex<double> cd;
// const int M = 998244353;
 
// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);
 
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
 
inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}
 
template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}
typedef array<int,4> arr4;
int const n_max=3e5+10;

set<int> zero;
//char s[n_max];
arr4 arr[3*n_max];
int ans[n_max];
int cnt=0;
int fen[n_max];
void upd(int idx,int val)
{
    for(;idx<n_max;idx+=idx&-idx)fen[idx]+=val;
}
int qr(int idx)
{
    int ret=0;
    for(idx;idx;idx-=idx&-idx)ret+=fen[idx];
    return ret;
}
void sol(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1,p=l;
    sol(l,mid);sol(mid+1,r);
    for(int i=mid+1;i<=r;i++)
    {
        if(arr[i][2])continue;
        while(p<=mid&&arr[p][1]>=arr[i][1]){upd(arr[p][3],arr[p][2]),p++;}
        ans[arr[i][3]]+=qr(arr[i][3]);
    }
    for(int i=l;i<p;i++)
    {
        upd(arr[i][3],-arr[i][2]);
    }
    inplace_merge(arr+l,arr+mid+1,arr+r+1,[&](const arr4 &a,const arr4 &b)
    {return a[1]>b[1];});
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(ans,-1,sizeof(ans));
    string s;
    int n,q;
    //scanf("%d%d%s",&n,&q,s+1);
    cin>>n>>q>>s;
    zero.insert(0);
    for(int i=0;i<n;i++)
    { 
        if(!(s[i]-='0'))zero.insert(i+1);
    }
    zero.insert(n+1);
    //char com[10];
    string com;
    for(int i=1;i<=q;i++)
    {
        //scanf("%s",com);
        cin>>com;
        if(com[0]=='q')
        {
            int a,b;
            //scanf("%d%d",&a,&b);
            cin>>a>>b;
            b--;
            arr[cnt++]={a,b,0,i};
            ans[i]=*zero.lower_bound(a)<=b? 0:i;
        }
        else
        {
            int a;
            //scanf("%d",&a);
            cin>>a;
            if(s[a-1])
            {
                auto it=zero.upper_bound(a);
                int l=*prev(it),m=a,r=*it;
                arr[cnt++]={l+1,r-1,i,i};
                arr[cnt++]={l+1,m-1,-i,i};
                arr[cnt++]={m+1,r-1,-i,i};
                zero.insert(a);
            }
            else
            {
                auto it=zero.find(a);
                int l=*prev(it),m=a,r=*next(it);
                arr[cnt++]={l+1,r-1,-i,i};
                arr[cnt++]={l+1,m-1,i,i};
                arr[cnt++]={m+1,r-1,i,i};
                zero.erase(it);
            }
            s[a-1]^=1;
        }
    }
    sort(arr, arr+cnt, [&](const arr4 &a, const arr4 &b)
    {return a[0]^b[0] ? a[0]<b[0] : ((a[1]!=b[1])? a[1]>b[1]:(b[2]==0)); });
    sol(0,cnt-1);
    for(int i=1;i<=q;i++)
    {
        if(ans[i]==-1)continue;
        else cout<<ans[i]<<"\n";//printf("%d\n",ans[i]);
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int qr(int)':
street_lamps.cpp:97:9: warning: statement has no effect [-Wunused-value]
   97 |     for(idx;idx;idx-=idx&-idx)ret+=fen[idx];
      |         ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 22356 KB Output is correct
2 Correct 303 ms 22456 KB Output is correct
3 Correct 270 ms 23916 KB Output is correct
4 Correct 308 ms 31888 KB Output is correct
5 Correct 311 ms 30028 KB Output is correct
6 Correct 318 ms 33444 KB Output is correct
7 Correct 314 ms 31680 KB Output is correct
8 Correct 199 ms 16172 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 395 ms 44868 KB Output is correct
6 Correct 355 ms 39004 KB Output is correct
7 Correct 352 ms 28832 KB Output is correct
8 Correct 303 ms 16420 KB Output is correct
9 Correct 227 ms 11336 KB Output is correct
10 Correct 250 ms 15028 KB Output is correct
11 Correct 257 ms 15160 KB Output is correct
12 Correct 438 ms 31020 KB Output is correct
13 Correct 309 ms 16420 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 415 ms 23576 KB Output is correct
6 Correct 368 ms 28184 KB Output is correct
7 Correct 344 ms 33376 KB Output is correct
8 Correct 302 ms 37664 KB Output is correct
9 Correct 251 ms 25912 KB Output is correct
10 Correct 231 ms 29380 KB Output is correct
11 Correct 251 ms 27452 KB Output is correct
12 Correct 229 ms 29164 KB Output is correct
13 Correct 248 ms 26120 KB Output is correct
14 Correct 232 ms 29228 KB Output is correct
15 Correct 453 ms 30356 KB Output is correct
16 Correct 325 ms 16944 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 373 ms 22356 KB Output is correct
9 Correct 303 ms 22456 KB Output is correct
10 Correct 270 ms 23916 KB Output is correct
11 Correct 308 ms 31888 KB Output is correct
12 Correct 311 ms 30028 KB Output is correct
13 Correct 318 ms 33444 KB Output is correct
14 Correct 314 ms 31680 KB Output is correct
15 Correct 199 ms 16172 KB Output is correct
16 Correct 2 ms 4440 KB Output is correct
17 Correct 2 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 395 ms 44868 KB Output is correct
21 Correct 355 ms 39004 KB Output is correct
22 Correct 352 ms 28832 KB Output is correct
23 Correct 303 ms 16420 KB Output is correct
24 Correct 227 ms 11336 KB Output is correct
25 Correct 250 ms 15028 KB Output is correct
26 Correct 257 ms 15160 KB Output is correct
27 Correct 438 ms 31020 KB Output is correct
28 Correct 309 ms 16420 KB Output is correct
29 Correct 2 ms 4444 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 2 ms 4440 KB Output is correct
32 Correct 2 ms 4440 KB Output is correct
33 Correct 415 ms 23576 KB Output is correct
34 Correct 368 ms 28184 KB Output is correct
35 Correct 344 ms 33376 KB Output is correct
36 Correct 302 ms 37664 KB Output is correct
37 Correct 251 ms 25912 KB Output is correct
38 Correct 231 ms 29380 KB Output is correct
39 Correct 251 ms 27452 KB Output is correct
40 Correct 229 ms 29164 KB Output is correct
41 Correct 248 ms 26120 KB Output is correct
42 Correct 232 ms 29228 KB Output is correct
43 Correct 453 ms 30356 KB Output is correct
44 Correct 325 ms 16944 KB Output is correct
45 Correct 257 ms 17324 KB Output is correct
46 Correct 180 ms 18028 KB Output is correct
47 Correct 209 ms 21688 KB Output is correct
48 Correct 362 ms 31804 KB Output is correct
49 Execution timed out 5041 ms 18516 KB Time limit exceeded
50 Halted 0 ms 0 KB -