Submission #397907

#	Time	Username	Problem	Language	Result	Execution time	Memory
397907		qwerasdfzxcl	단층 (JOI16_ho_t5)	C++14	100 / 100	257 ms	13596 KiB

2016_ho_t5

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Seg{
    ll lazy[400400];
    int sz;
    void update(int l, int r, ll val){
        for(l += sz, r += sz;l<r;l>>=1, r>>=1){
            if (l&1) lazy[l++] += val;
            if (r&1) lazy[--r] += val;
        }
    }
    ll query(int x){
        ll ret = lazy[x+=sz];
        for (x>>=1;x;x>>=1) ret += lazy[x];
        return ret;
    }
}tree1, tree2;
struct Query{
    int x, d;
    ll l;
}query[200200];

int main(){
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i=0;i<q;i++) scanf("%d %d %lld", &query[i].x, &query[i].d, &query[i].l);
    tree1.sz = n, tree2.sz = n;
    for (int i=q-1;i>=0;i--){
        if (query[i].d==1){
            int l = 0, r = n, idx=0;
            while(l!=r){
                int m = (l+r)/2;
                ll tmp = tree1.query(m)*2-m;
                if (tmp>-query[i].x){
                    idx = m+1;
                    l = m+1;
                }
                else r = m;
            }
            //printf("1 %d %d\n", i, idx);
            tree2.update(0, idx, -query[i].l);
        }
        else{
            int l = 0, r = n, idx = n;
            while(l!=r){
                int m = (l+r)/2;
                ll tmp = tree2.query(m)*2+m;
                if (tmp>=query[i].x){
                    idx = m;
                    r = m;
                }
                else l = m+1;
            }
            //printf("2 %d %d\n", i, idx);
            tree1.update(idx, n, -query[i].l);
        }
    }
    for (int i=0;i<n;i++){
        ll ans = tree1.query(i) + tree2.query(i);
        printf("%lld\n", -ans);
    }
    return 0;
}

Compilation message (stderr)

2016_ho_t5.cpp: In function 'int main()':
2016_ho_t5.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
2016_ho_t5.cpp:28:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     for (int i=0;i<q;i++) scanf("%d %d %lld", &query[i].x, &query[i].d, &query[i].l);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66