Submission #973136

#	Time	Username	Problem	Language	Result	Execution time	Memory
973136		Unforgettablepl	Strange Device (APIO19_strange_device)	C++17	0 / 100	7 ms	13440 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct Lazy{
    bool type;
    int amount;
    Lazy(){}
    Lazy(bool a,int b):type(a),amount(b){}
    Lazy add(Lazy other){
        if(other.type)return other;
        return {type,amount+other.amount};
    }
};

Lazy lazy[600001];
int tree[600001];

void update(bool type,int a,int b,int x,int k,int L,int R){
    if(lazy[k].amount or lazy[k].type){
        if(lazy[k].type)tree[k] = 0;
        tree[k] += (R-L+1ll)*lazy[k].amount;
        if(L!=R){
            lazy[2*k] = lazy[2*k].add(lazy[k]);
            lazy[2*k+1] = lazy[2*k+1].add(lazy[k]);
        }
        lazy[k].type = false;
        lazy[k].amount = 0;
    }
    if(a>R or b<L)return;
    if(L==R){
        if(type)tree[k]=x;
        else tree[k]+=x;
        return;
    }
    if(a<=L and R<=b){
        if(type)tree[k]=0;
        tree[k]+=(R-L+1ll)*x;
        lazy[2*k]=lazy[2*k].add({type,x});
        lazy[2*k+1]=lazy[2*k+1].add({type,x});
        return;
    }
    int mid = (L+R)/2;
    update(type,a,b,x,2*k,L,mid);
    update(type,a,b,x,2*k+1,mid+1,R);
    tree[k] = tree[2*k]+tree[2*k+1];
}

int get(int a,int b,int k,int L,int R) {
    if (a > R or b < L)return 0;
    if (lazy[k].amount or lazy[k].type) {
        if (lazy[k].type)tree[k] = 0;
        tree[k] += (R - L + 1ll) * lazy[k].amount;
        if (L != R) {
            lazy[2 * k] = lazy[2 * k].add(lazy[k]);
            lazy[2 * k + 1] = lazy[2 * k + 1].add(lazy[k]);
        }
        lazy[k].type = false;
        lazy[k].amount = 0;
    }
    if (a <= L and R <= b)return tree[k];
    int mid = (L + R) / 2;
    return get(a, b, 2 * k, L, mid) + get(a, b, 2 * k + 1, mid + 1, R);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int&i:tree)i=INT32_MAX;
    int n,A,B;
    cin >> n >> A >> B;
    if(A%2==0)A/=2;
    // update(true,l,r,amount,1,1,n)
    for(int i=1;i<=n;i++){
        int l,r;cin>> l >> r;
        int block_l = l/A;
        int block_r = r/A;
        l%=A;
        r%=A;
        if(block_l==block_r){
            update(true,l,r,1,1,0,A-1);
        } else if(block_l+1==block_r){
            update(true,l,A-1,1,1,0,A-1);
            update(true,0,r,1,1,0,A-1);
        } else {
            cout << A << '\n';
            return 0;
        }
    }
    cout << get(0,A-1,1,0,A-1) << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30