結果

問題 No.3411 Range Clamp Sum
コンテスト
ユーザー The Forsaking
提出日時 2025-12-21 22:45:24
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 830 ms / 10,000 ms
コード長 2,115 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,910 ms
コンパイル使用メモリ 206,644 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-21 22:45:41
合計ジャッジ時間 15,322 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:21:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   21 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
main.cpp:22:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |     for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
      |                                     ~~~~~^~~~~~~~~~~~~
main.cpp:33:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
main.cpp:35:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |             scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
main.cpp:45:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |             scanf("%d%d%d%d", &l, &r, &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];


struct Node {
    int l, r;
    vector<int> v;
    vector<ll> s;
    bool operator<(const Node& w) {
        return r < w.r;
    }
};
int main() {
    const int mid = 316;
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
    vector<Node> e;
    for (int i = 0; i * mid + 1 <= n; i++) {
        e.push_back({i * mid + 1, min(n, (i + 1) * mid), {}, {}});
        auto& u = e.back();
        for (int j = i * mid + 1; j <= min(n, (i + 1) * mid); j++) u.v.push_back(w[j]);
        sort(u.v.begin(), u.v.end());
        for (int j = 0; j < u.v.size(); j++) u.s.push_back(j ? u.s[j - 1] + u.v[j] : u.v[j]);
    }
    while (m--) {
        int op, l, r, a, b;
        scanf("%d", &op);
        if (op & 1) {
            scanf("%d%d", &a, &b);
            auto& u = *lower_bound(e.begin(), e.end(), Node{0, a, {}, {}});
            for (int i = 0; i < u.v.size(); i++)
                if (u.v[i] == w[a]) {
                    u.v[i] = w[a] = b;
                    break;
                }
            sort(u.v.begin(), u.v.end());
            for (int j = 0; j < u.v.size(); j++) u.s[j] = (j ? u.s[j - 1] + u.v[j] : u.v[j]);
        } else {
            scanf("%d%d%d%d", &l, &r, &a, &b);
            ll res = 0;
            auto u = lower_bound(e.begin(), e.end(), Node{0, l, {}, {}});
            while (u != e.end() && u->l <= r) {
                if (u->l >= l && u->r <= r) {
                    auto x = lower_bound(u->v.begin(), u->v.end(), a), y = upper_bound(u->v.begin(), u->v.end(), b);
                    res += (x - u->v.begin()) * (ll)a + (u->v.end() - y) * (ll)b;
                    if (y > x) res += u->s[y - u->v.begin() - 1] - (x != u->v.begin() ? u->s[x - u->v.begin() - 1] : 0);
                } else for (int i = max(l, u->l); i <= min(r, u->r); i++) res = res + max(a, min(b, w[i]));
                ++u;
            }
            printf("%lld\n", res);
        }
    }   
    return 0;
}
0