oj.uz

답안 #329211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329211 2020-11-19T21:47:26 Z iliccmarko Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 857 ms 69344 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)
{
    seg[node].erase(pos);
    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)
{
    seg[node].insert(pos);
    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;
    int ss = q;
    int cnt = 0;
    vector<pair<int, pair<int, int> > > sss;
    while(ss--)
    {
        int s, t, u;
        cin>>s>>t>>u;
        if(s==3)
            cnt++;
        sss.pb({s, {t, u}});
    }
    int i = 0;
    while(q--)
    {
        int s, t, u;
        s = sss[i].first;
        t = sss[i].second.first;
        u = sss[i].second.second;
        i++;
        //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
            if(k==1) continue;
            set<int> qq = get_alive(0, t, u, 0, n-1);
            for(int x : qq)
            {
                //cout<<x<<" ";
                //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;
            //cout<<endl;
        }
        else{
            // ispisi sumu od l do r
            //cout<<u<<" "<<t<<endl;
            cnt--;
            cout<<get_sum(0, t, u, 0, n-1);
            if(cnt)
                cout<<endl;
        }
    }




    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23048 KB Output is correct
2 Correct 134 ms 38080 KB Output is correct
3 Correct 163 ms 38904 KB Output is correct
4 Correct 210 ms 31456 KB Output is correct
5 Correct 449 ms 66016 KB Output is correct
6 Correct 451 ms 65252 KB Output is correct
7 Correct 479 ms 64868 KB Output is correct
8 Correct 489 ms 65536 KB Output is correct
9 Correct 433 ms 69344 KB Output is correct
10 Correct 392 ms 69124 KB Output is correct
11 Correct 453 ms 69236 KB Output is correct
12 Correct 419 ms 69344 KB Output is correct

Subtask #4
0 / 75.0

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