oj.uz

답안 #329079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329079 2020-11-19T00:11:27 Z iliccmarko Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 66968 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
int n, q, k;
const int N = 1e5 + 5;
set<int> seg[4*N];
int sum[4*N];
vector<int> a(N);

int get_sum(int node, int l, int r, int i, int j)
{
    if(i>r||j<l) return 0;
    if(i>=l&&j<=r) return sum[node];
    int mid = (i+j)/2;
    return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}

void update(int node, int l, int r, int pos, int x)
{
    if(l==r)
    {
        sum[node] = x;
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid)
        update(node*2+2, mid+1, r, pos, x);
    else
        update(node*2+1, l, mid, pos, x);
    sum[node] = sum[node*2+1] + sum[node*2+2];
}

void build(int node, int l, int r)
{
    if(l==r)
    {
        if(a[l])
        seg[node].insert(l);
        return;
    }
    for(int s = l;s<=r;s++)
        if(a[s]) seg[node].insert(s);
    int mid = (l+r)/2;
    build(node*2+1, l, mid);
    build(node*2+2, mid+1, r);
}

int build_sum(int node, int l, int r)
{
    if(l==r)
    {
       return sum[node] = a[l];
    }
    int mid = (l+r)/2;
    return sum[node] = build_sum(node*2+1, l, mid) + build_sum(node*2+2, mid+1, r);
}

void _erase(int node, int l, int r, int pos, int x)
{
    if(pos>=l&&pos<=r)
        seg[node].erase(x);
    if(l==r)
        return;
    int mid = (l+r)/2;
    if(pos>mid)
        _erase(node*2+2, mid+1, r, pos, x);
    else
        _erase(node*2+1, l, mid, pos, x);
}

void _insert(int node, int l, int r, int pos, int x)
{
    if(pos>=l&&pos<=r) seg[node].insert(x);
    if(l==r)
        return;
    int mid = (l+r)/2;
    if(pos>mid)
        _insert(node*2+2, mid+1, r, pos, x);
    else
        _insert(node*2+1, l, mid, pos, x);
}

set<int> get_alive(int node, int l, int r, int i, int j)
{
    if(i>r||j<l) {
        set<int> q;
        return q;
    }
    if(i>=l&&j<=r)
        return seg[node];
    int mid = (i+j)/2;
    set<int> levo = get_alive(node*2+1, l, r, i, mid);
    set<int> desno = get_alive(node*2+2, l, r, mid+1, j);
    set<int> ans;
    for(int x : levo)
        ans.insert(x);
    for(int x : desno)
        ans.insert(x);
    return ans;
}

int main()
{
    ios
    cin>>n>>q>>k;
    for(int i = 0;i<n;i++)
        cin>>a[i];
    build(0, 0, n-1);
    //cout<<11111<<endl;
    build_sum(0, 0, n-1);
    //cout<<2222<<endl;
    while(q--)
    {
        int s, t, u;
        //line
        cin>>s>>t>>u;
        t--;
        u--;
        if(s==1)
        {
            // a-ti tanjir na b
            u++;
            if(!a[t]&&u)
                _insert(0, 0, n-1, t, t);
            if(a[t]&&!u)
                _erase(0, 0, n-1, t, t);
            a[t] = u;
            update(0, 0, n-1, t, u);
        }
        else if(s==2)
        {
            // sprej
            set<int> qq = get_alive(0, t, u, 0, n-1);
            for(int x : qq)
            {
                //cout<<x<<" ";
                a[x] /= k;
                if(!a[x])
                    _erase(0, 0, n-1, x, x);
                update(0, 0, n-1, x, a[x]);
            }
            //cout<<endl;
        }
        else{
            // ispisi sumu od l do r
            //cout<<u<<" "<<t<<endl;
            cout<<get_sum(0, t, u, 0, n-1)<<endl;
        }
    }




    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 19564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5077 ms 63212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 22252 KB Output is correct
2 Correct 127 ms 37868 KB Output is correct
3 Correct 143 ms 38720 KB Output is correct
4 Correct 171 ms 30316 KB Output is correct
5 Correct 409 ms 64876 KB Output is correct
6 Correct 414 ms 64108 KB Output is correct
7 Execution timed out 5081 ms 66968 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 832 ms 65900 KB Output isn't correct
2 Halted 0 ms 0 KB -