Submission #8194295

---

Source Code Expand

// ※※※ 解答不能 ※※※
// yutaka1999氏.
// https://atcoder.jp/contests/dwango2015-prelims/submissions/828744
#include <bits/stdc++.h>
using namespace std;
#define SIZE 4005
typedef long long int ll;
typedef pair <ll, ll> P;
typedef pair <ll, P> PP;
vector <ll> vx;
ll A[SIZE], B[SIZE], C[SIZE], D[SIZE], E[SIZE], F[SIZE];
vector <P> query[SIZE];
vector <PP> vec[SIZE], vec2[SIZE];
vector <ll> sum[SIZE];

int main(){
    int m;
    ll n;
    scanf("%lld %d",&n,&m);
    for(int i = 0; i < m; i++){
        ll a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        ll x = b - 1;
        ll y = n - (a + c - 1);
        A[i] = x, B[i] = y, C[i] = c;
        vx.push_back(A[i]);
        vx.push_back(A[i] + C[i]);
    }
    int q;
    scanf("%d",&q);
    for(int i = 0; i < q; i++){
        ll a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        ll x = b - 1;
        ll y = n - (a + c - 1);
        D[i] = x, E[i] = y, F[i] = c;
        vx.push_back(D[i]);
        vx.push_back(D[i] + F[i]);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    for(int i = 0; i < m; i++){
        int pos = lower_bound(vx.begin(), vx.end(), A[i]) - vx.begin();
        while(vx[pos] < A[i] + C[i]){
            ll h = A[i] + C[i] - vx[pos + 1];
            query[pos].push_back(P(B[i], h));
            pos++;
        }
    }
    for(int i = 0; i + 1 < vx.size(); i++){
        sort(query[i].begin(), query[i].end());
        ll now = 0;
        ll w = vx[i + 1] - vx[i];
        for(int j=0;j<query[i].size();){
            ll h = query[i][j].second;
            ll bot = query[i][j].first;
            for(;j < query[i].size() && bot + h + 1 >= query[i][j].first; j++){
                h = max(h, query[i][j].first + query[i][j].second - bot);
            }
            ll len = w;
            if(j < query[i].size()) len = min(len, query[i][j].first - (bot + h));
            now += w * (h + len) - len * (len - 1) / 2LL;
            vec[i].push_back(PP(bot + h + len, P(h, len)));
            vec2[i].push_back(PP(bot + h, P(h, len)));
            sum[i].push_back(now);
        }
    }
    for(int i = 0; i < q; i++){
        ll ans = 0;
        int pos = lower_bound(vx.begin(), vx.end(), D[i]) - vx.begin();
        while(vx[pos] < D[i] + F[i]){
            ll h = D[i] + F[i] - vx[pos + 1], w = vx[pos + 1] - vx[pos];
            // 下の部分を引く
            int down = lower_bound(vec[pos].begin(), vec[pos].end(), PP(E[i] + 1, P(-1, -1))) - vec[pos].begin();
            if(down > 0) ans -= sum[pos][down-1];
            if(down < vec[pos].size()){
                PP p = vec[pos][down];
                ll h2 = p.second.first, l2 = p.second.second;
                ll d2 = p.first - (h2 + l2);
                if(d2 < E[i]){
                    if(d2 + h2 >= E[i]){
                        ans -= w * (E[i] - d2);
                    }else{
                        ans -= w * h2;
                        ll len = E[i] - (d2 + h2);
                        assert(len <= l2);
                        ans -= w * len - len * (len - 1) / 2LL;
                    }
                }
            }
            // 斜線以下を足す
            int up = lower_bound(vec2[pos].begin(), vec2[pos].end(), PP(E[i] + h + 1, P(-1, -1))) - vec2[pos].begin();
            if(up > 0) ans += sum[pos][up - 1];
            if(up<vec2[pos].size()){
                PP p = vec2[pos][up];
                ll h2 = p.second.first, l2 = p.second.second;
                ll d2 = p.first-h2;
                if(d2 <= E[i] + h + w - 1){
                    ans += w * (w + 1) / 2LL;
                    if(d2 >= E[i] + h){
                        ll b = d2 - (E[i] + h);
                        ans -= w * b - b * (b - 1) / 2LL;
                    }else{
                        ans += w * (E[i] + h - d2);
                    }
                }
            }
            pos++;
        }
        ll all = F[i] * (F[i] + 1) / 2LL;
        assert(all - ans >= 0 && ans >= 0);
        printf("%lld\n",all - ans);
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:19:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %d",&n,&m);
                           ^
./Main.cpp:22:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &a, &b, &c);
                                            ^
./Main.cpp:30:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
./Main.cpp:33:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &a, &b, &c);
                                            ^

Judge Result