dwangoプログラミングコンテスト

Submission #8194295

Source codeソースコード

// ※※※ 解答不能 ※※※
// 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

Task問題 E - 電波局
User nameユーザ名 at_abcde
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 4199 Byte
File nameファイル名
Exec time実行時間 186 ms
Memory usageメモリ使用量 42368 KB

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0-sample-01.txt,subtask0-sample-02.txt
Subtask1 10 / 10 subtask0-sample-01.txt,subtask0-sample-02.txt,subtask1-01.txt,subtask1-02.txt,subtask1-03.txt,subtask1-04.txt,subtask1-05.txt,subtask1-06.txt,subtask1-07.txt,subtask1-08.txt,subtask1-09.txt,subtask1-10.txt,subtask1-11.txt,subtask1-12.txt,subtask1-13.txt,subtask1-14.txt,subtask1-15.txt,subtask1-16.txt,subtask1-17.txt,subtask1-18.txt,subtask1-19.txt,subtask1-20.txt
Subtask2 30 / 30 subtask0-sample-01.txt,subtask0-sample-02.txt,subtask1-01.txt,subtask1-02.txt,subtask1-03.txt,subtask1-04.txt,subtask1-05.txt,subtask1-06.txt,subtask1-07.txt,subtask1-08.txt,subtask1-09.txt,subtask1-10.txt,subtask1-11.txt,subtask1-12.txt,subtask1-13.txt,subtask1-14.txt,subtask1-15.txt,subtask1-16.txt,subtask1-17.txt,subtask1-18.txt,subtask1-19.txt,subtask1-20.txt,subtask2-01.txt,subtask2-02.txt,subtask2-03.txt,subtask2-04.txt,subtask2-05.txt,subtask2-06.txt,subtask2-07.txt,subtask2-08.txt,subtask2-09.txt,subtask2-10.txt,subtask2-11.txt,subtask2-12.txt,subtask2-13.txt,subtask2-14.txt,subtask2-15.txt,subtask2-16.txt,subtask2-17.txt,subtask2-18.txt,subtask2-19.txt,subtask2-20.txt
Subtask3 60 / 60 subtask0-sample-01.txt,subtask0-sample-02.txt,subtask1-01.txt,subtask1-02.txt,subtask1-03.txt,subtask1-04.txt,subtask1-05.txt,subtask1-06.txt,subtask1-07.txt,subtask1-08.txt,subtask1-09.txt,subtask1-10.txt,subtask1-11.txt,subtask1-12.txt,subtask1-13.txt,subtask1-14.txt,subtask1-15.txt,subtask1-16.txt,subtask1-17.txt,subtask1-18.txt,subtask1-19.txt,subtask1-20.txt,subtask2-01.txt,subtask2-02.txt,subtask2-03.txt,subtask2-04.txt,subtask2-05.txt,subtask2-06.txt,subtask2-07.txt,subtask2-08.txt,subtask2-09.txt,subtask2-10.txt,subtask2-11.txt,subtask2-12.txt,subtask2-13.txt,subtask2-14.txt,subtask2-15.txt,subtask2-16.txt,subtask2-17.txt,subtask2-18.txt,subtask2-19.txt,subtask2-20.txt,subtask3-01.txt,subtask3-02.txt,subtask3-03.txt,subtask3-04.txt,subtask3-05.txt,subtask3-06.txt,subtask3-07.txt,subtask3-08.txt,subtask3-09.txt,subtask3-10.txt,subtask3-11.txt,subtask3-12.txt,subtask3-13.txt,subtask3-14.txt,subtask3-15.txt,subtask3-16.txt,subtask3-17.txt,subtask3-18.txt,subtask3-19.txt,subtask3-20.txt,subtask3-21.txt,subtask3-22.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0-sample-01.txt AC 2 ms 640 KB
subtask0-sample-02.txt AC 1 ms 640 KB
subtask1-01.txt AC 1 ms 640 KB
subtask1-02.txt AC 2 ms 640 KB
subtask1-03.txt AC 2 ms 640 KB
subtask1-04.txt AC 2 ms 896 KB
subtask1-05.txt AC 2 ms 640 KB
subtask1-06.txt AC 2 ms 640 KB
subtask1-07.txt AC 2 ms 640 KB
subtask1-08.txt AC 2 ms 896 KB
subtask1-09.txt AC 3 ms 1024 KB
subtask1-10.txt AC 2 ms 640 KB
subtask1-11.txt AC 2 ms 896 KB
subtask1-12.txt AC 2 ms 640 KB
subtask1-13.txt AC 2 ms 896 KB
subtask1-14.txt AC 2 ms 896 KB
subtask1-15.txt AC 3 ms 1024 KB
subtask1-16.txt AC 2 ms 896 KB
subtask1-17.txt AC 2 ms 896 KB
subtask1-18.txt AC 2 ms 896 KB
subtask1-19.txt AC 2 ms 640 KB
subtask1-20.txt AC 3 ms 896 KB
subtask2-01.txt AC 2 ms 640 KB
subtask2-02.txt AC 2 ms 640 KB
subtask2-03.txt AC 7 ms 2560 KB
subtask2-04.txt AC 2 ms 640 KB
subtask2-05.txt AC 7 ms 2560 KB
subtask2-06.txt AC 7 ms 2304 KB
subtask2-07.txt AC 7 ms 2176 KB
subtask2-08.txt AC 2 ms 640 KB
subtask2-09.txt AC 5 ms 1920 KB
subtask2-10.txt AC 8 ms 2560 KB
subtask2-11.txt AC 5 ms 1792 KB
subtask2-12.txt AC 2 ms 640 KB
subtask2-13.txt AC 7 ms 2176 KB
subtask2-14.txt AC 7 ms 2560 KB
subtask2-15.txt AC 2 ms 640 KB
subtask2-16.txt AC 5 ms 1920 KB
subtask2-17.txt AC 2 ms 640 KB
subtask2-18.txt AC 7 ms 2176 KB
subtask2-19.txt AC 5 ms 1920 KB
subtask2-20.txt AC 2 ms 640 KB
subtask3-01.txt AC 5 ms 640 KB
subtask3-02.txt AC 82 ms 20224 KB
subtask3-03.txt AC 92 ms 22656 KB
subtask3-04.txt AC 184 ms 42368 KB
subtask3-05.txt AC 20 ms 896 KB
subtask3-06.txt AC 21 ms 896 KB
subtask3-07.txt AC 186 ms 41856 KB
subtask3-08.txt AC 158 ms 34816 KB
subtask3-09.txt AC 160 ms 35456 KB
subtask3-10.txt AC 91 ms 22144 KB
subtask3-11.txt AC 161 ms 35968 KB
subtask3-12.txt AC 92 ms 22528 KB
subtask3-13.txt AC 21 ms 896 KB
subtask3-14.txt AC 20 ms 896 KB
subtask3-15.txt AC 161 ms 35712 KB
subtask3-16.txt AC 183 ms 42112 KB
subtask3-17.txt AC 103 ms 26240 KB
subtask3-18.txt AC 22 ms 896 KB
subtask3-19.txt AC 21 ms 896 KB
subtask3-20.txt AC 93 ms 22912 KB
subtask3-21.txt AC 165 ms 35712 KB
subtask3-22.txt AC 166 ms 35712 KB