QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226535#6227. 区间和SorahISA25 290ms24484kbC++2012.1kb2023-10-26 02:50:252023-10-26 02:50:25

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 02:50:25]
  • 评测
  • 测评结果:25
  • 用时:290ms
  • 内存:24484kb
  • [2023-10-26 02:50:25]
  • 提交

answer

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

const int INF = 1E9 + 10;

struct SegBeats {
    
    struct Node {
        int min1, min2, min_cnt, pmax, pmax_id, smax, smax_id, mss, sum, tag;
        Node() : min1(INF), min2(INF), min_cnt(0), pmax(0), pmax_id(-1), smax(0), smax_id(0), mss(0), sum(0), tag(-INF) {}
        Node(int val, int id) :
            min1(val), min2(INF), min_cnt(1),
            pmax(val >= 0 ? val : 0), pmax_id(val >= 0 ? id : id-1),
            smax(val >= 0 ? val : 0), smax_id(val >= 0 ? id : id+1),
            mss(val >= 0 ? val : 0), sum(val), tag(-INF) {}
    };
    
    vector<Node> seg;
    int maxn;
    
    void init(int N, const vector<int> &vec) {
        maxn = (1 << (__lg(N+1) + 1));
        seg.assign(2*maxn, Node());
        for (int i = 0; i < maxn; ++i) seg[i+maxn] = Node((i < SZ(vec) ? vec[i] : 0), i);
        for (int i = maxn-1; i >= 1; --i) pull(seg[i], seg[i<<1], seg[i<<1|1]);
    }
    
    void push(Node &a, Node &l, Node &r, int now, int nL, int nR) {
        int nM = (nL + nR) >> 1;
        if (a.tag > l.min1) {
            l.sum += (a.tag - l.min1) * l.min_cnt;
            l.min1 = l.tag = a.tag;
            if (l.pmax_id < nM) l.pmax_id = query_node(l.pmax_id + 1, nM, now<<1, nL, nM).pmax_id;
            l.pmax = (nL <= l.pmax_id ? query_node(nL, l.pmax_id, now<<1, nL, nM).sum : 0);
            if (l.smax_id > nL) l.smax_id = query_node(nL, l.smax_id - 1, now<<1, nL, nM).smax_id;
            l.smax = (nM >= l.smax_id ? query_node(l.pmax_id, nM, now<<1, nL, nM).sum : 0);
        }
        if (a.tag > r.min1) {
            r.sum += (a.tag - r.min1) * r.min_cnt;
            r.min1 = r.tag = a.tag;
            if (r.pmax_id < nR)   r.pmax_id = query_node(r.pmax_id + 1, nR,   now<<1|1, nM+1, nR).pmax_id;
            r.pmax = (nM <  r.pmax_id ? query_node(nM+1, r.pmax_id, now<<1|1, nM+1, nR).sum : 0);
            if (r.smax_id > nM+1) r.smax_id = query_node(nM+1, r.smax_id - 1, now<<1|1, nM+1, nR).smax_id;
            r.smax = (nR >= r.smax_id ? query_node(r.pmax_id, nR,   now<<1|1, nM+1, nR).sum : 0);
        }
        a.tag = -INF;
    }
    
    void pull(Node &a, Node &l, Node &r) {
        a.min1 = min(l.min1, r.min1);
        a.min2 = (l.min1 == r.min1 ? min(l.min2, r.min2) : (l.min1 < r.min1 ? min(l.min2, r.min1) : min(l.min1, r.min2)));
        a.min_cnt = l.min_cnt * (l.min1 == a.min1) + r.min_cnt * (r.min1 == a.min1);
        a.pmax = max(l.pmax, l.sum + r.pmax);
        a.pmax_id = (l.pmax == a.pmax ? l.pmax_id : r.pmax_id);
        a.smax = max(r.smax, r.sum + l.smax);
        a.smax_id = (r.smax == a.smax ? r.smax_id : l.smax_id);
        a.mss = max({l.mss, r.mss, l.smax + r.pmax});
        a.sum = l.sum + r.sum;
        a.tag = -INF;
    }
    
    Node query_node(int qL, int qR) { return query_node(qL, qR, 1, 0, maxn-1); }
    Node query_node(int qL, int qR, int now, int nL, int nR) {
        if (qL <= nL and nR <= qR) return seg[now];
        
        push(seg[now], seg[now<<1], seg[now<<1|1], now, nL, nR);
        
        int nM = (nL + nR) >> 1;
        
        Node tmp, l, r;
        if (qL <= nM) l = query_node(qL, qR, now<<1,   nL,   nM);
        if (nM <  qR) r = query_node(qL, qR, now<<1|1, nM+1, nR);
        pull(tmp, l, r);
        
        pull(seg[now], seg[now<<1], seg[now<<1|1]);
        
        return tmp;
    }
    
    void modify_range_chmax(int qL, int qR, int val) { return modify_range_chmax(qL, qR, val, 1, 0, maxn-1); }
    void modify_range_chmax(int qL, int qR, int val, int now, int nL, int nR) {
        if (qL <= nL and nR <= qR and val <= seg[now].min1) return;
        if (qL <= nL and nR <= qR and val < seg[now].min2) {
            seg[now].sum += (val - seg[now].min1) * seg[now].min_cnt;
            seg[now].min1 = seg[now].tag = val;
            if (seg[now].pmax_id < nR) seg[now].pmax_id = query_node(seg[now].pmax_id + 1, nR, now, nL, nR).pmax_id;
            seg[now].pmax = (nL <= seg[now].pmax_id ? query_node(nL, seg[now].pmax_id, now, nL, nR).sum : 0);
            if (seg[now].smax_id > nL) seg[now].smax_id = query_node(nL, seg[now].smax_id - 1, now, nL, nR).smax_id;
            seg[now].smax = (nR >= seg[now].smax_id ? query_node(seg[now].smax_id, nR, now, nL, nR).sum : 0);
            return;
        }
        
        push(seg[now], seg[now<<1], seg[now<<1|1], now, nL, nR);
        
        int nM = (nL + nR) >> 1;
        if (qL <= nM) modify_range_chmax(qL, qR, val, now<<1,   nL,   nM);
        if (nM <  qR) modify_range_chmax(qL, qR, val, now<<1|1, nM+1, nR);
        
        pull(seg[now], seg[now<<1], seg[now<<1|1]);
    }
    
};

void solve() {
    int N, Q; cin >> N >> Q;
    
    vector<int> A(N);
    for (int &x : A) cin >> x;
    
    SegBeats seg; seg.init(N, A);
    
    for (int q = 1; q <= Q; ++q) {
        int op; cin >> op;
        if (op == 0) {
            int l, r, x; cin >> l >> r >> x, --l, --r;
            seg.modify_range_chmax(l, r, x);
        }
        if (op == 1) {
            int l, r; cin >> l >> r, --l, --r;
            print(seg.query_node(l, r).mss);
        }
    }
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.emplace_back("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
    fprintf(stdout, "%s", "\u001b[36m"), \
    _P(__VA_ARGS__), \
    fprintf(stdout, "%s", "\u001b[0m")

deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif

inline void _P() {cout << "\n";};
template <typename T> inline void _P(T &&_t) {cout << _t << "\n";}
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) {cout << _t << " ", _P(_u...);}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pop_back(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pop_back(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

#endif

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3536kb

input:

182 187
20634704 -703314946 -948946252 144678123 5498424 341678302 -583114991 -196836433 43951489 -525692929 12701289 476729334 473931783 221423816 187493596 355488624 -39527016 -914505949 161713515 -227399136 -318205061 226437730 -601354045 -755181154 -241221294 256834551 44488096 -422708891 -79709...

output:

270081855
539758298
933165833
539758298
933165833
933165833
415646256
1727768442
933165833
539758298
1727768442
1110244863
1110244863
933165833
933165833
1727768442
1110244863
1110244863
478904667
1110244863
883782633
8394442494
6275824497
51650758
1727768442
3992159989
1727768442
4577425791
8476934...

result:

wrong answer 3rd lines differ - expected: '1110244863', found: '933165833'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3452kb

input:

195 195
248663111 -522337032 -47794804 -955243356 418601542 493840666 478655582 -269027492 -801169819 -410940079 -766532109 -547019833 -158802702 -193483181 -125250985 35351136 -47755604 -781346033 -613952400 -155863697 5685369 -620132917 222562003 -563874770 65617262 356362550 -311762774 86801383 -...

output:

1190435898
1190435898
639530621
639530621
639530621
639530621
1391097790
1190435898
639530621
413488363
630930122
639530621
639530621
350877205
309588774
639530621
639530621
972496248
639530621
611410143
1190435898
579188534
1190435898
413488363
478655582
611410143
929409019
330633442
39062849
63953...

result:

wrong answer 10th lines differ - expected: '579188534', found: '413488363'

Subtask #3:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 2ms
memory: 3592kb

input:

1834 1935
-32669453 -670047955 -534537788 80759807 -678610903 -5993655 476471070 90341342 -187206225 -710992660 -837284426 -844649722 -846473433 123470247 177108533 -821700607 97488160 171075677 -146656769 -775261735 -464781034 -518041912 -668027329 -286982559 -108624782 483720318 -632815034 -881243...

output:

1137782164
774147943
1279874032
1267995234
1689668080
1267995234
893115370
1446237023
1267995234
1294914714
697506760
868107303
712660432
1446237023
1137805811
701684754
1137805811
1294914714
1137805811
1294914714
930499732
1267995234
930499732
10445269872
10445269872
10445269872
10445269872
1044526...

result:

wrong answer 6th lines differ - expected: '1279874032', found: '1267995234'

Subtask #4:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 3576kb

input:

1893 1857
-575490410 -790871182 -488011488 -321041425 238235943 262471772 -469848975 -105728328 62479104 19449896 54374656 91107269 125781673 251316981 -264727698 -933332817 315892884 -117300817 -826569250 -156322407 -109499160 202312868 264008468 -814436982 -431822419 -791224962 -67966257 407973223...

output:

936342527
1833261811
1833261811
1833261811
1073428714
1833261811
1073428714
1762929123
1746727467
1746727467
1746727467
1746727467
1571697835
1073428714
1746727467
1746727467
12232324898
61547147263
45295265069
61547147263
444826397143
58754678356
622444335
84132616330
175182648647
399168235633
5761...

result:

wrong answer 8th lines differ - expected: '1833261811', found: '1762929123'

Subtask #5:

score: 5
Accepted

Test #7:

score: 5
Accepted
time: 103ms
memory: 24308kb

input:

97140 97922
75593863 -269004770 -675918045 472330615 -528175962 -580254086 -951270301 -544120385 -525052964 83784128 -226029062 -845875377 34756691 -952920941 -135400084 -20027657 -106558944 -855126948 46245866 -27672459 57802322 -834704313 -625678818 477028623 -9764793 -562713509 477554293 -7238437...

output:

1901808402
2589864136
2615472062
1901808402
2703782432
2703782432
2615472062
2615472062
2615472062
2067055974
2703782432
2615472062
2615472062
2615472062
2615472062
421081808
2615472062
1883490541
1883490541
2441176212
2067055974
2020462870
2615472062
2703782432
2441176212
2703782432
2299923583
2441...

result:

ok 48670 lines

Subtask #6:

score: 5
Accepted

Test #8:

score: 5
Accepted
time: 183ms
memory: 24468kb

input:

97981 186115
-226252189 -571234361 62844820 434180550 269963453 329910638 -847454849 112774660 -178914951 71306715 -859266500 -339120598 -962299988 -157196500 125308122 -668295657 -761232762 165342869 134196398 -767235541 -384052757 -305824813 199376354 226477587 -678798649 -885355596 -979742822 -84...

output:

1819183608
2495542993
2495542993
2084102650
2495542993
2220231814
2495542993
2220231814
2293866611
1927092471
1739879062
2495542993
2495542993
1923181637
2220231814
1494640322
2220231814
2495542993
1927092471
2495542993
1881136236
2495542993
2495542993
2495542993
2112346048
2495542993
2495542993
222...

result:

ok 92966 lines

Subtask #7:

score: 5
Accepted

Test #9:

score: 5
Accepted
time: 198ms
memory: 24348kb

input:

100000 200000
-372870627 -42874740 -537215664 -906588913 -835034566 -406645490 -54474616 -38917607 467210345 -993351739 450345098 12085867 -344729277 -480989044 388326288 -297525580 -259462382 -224591683 -948514660 -494880819 -13589765 -249884145 -387021275 471618602 291976233 358261225 -268906305 1...

output:

1841236083
2463913756
3170394596
3170394596
2463913756
2747069068
3170394596
3170394596
2747069068
3170394596
3170394596
3170394596
1875295477
2747069068
3170394596
3170394596
1868323991
2514664161
3170394596
2514664161
3170394596
3170394596
3170394596
3170394596
3170394596
1914135908
2747069068
317...

result:

ok 99715 lines

Subtask #8:

score: 5
Accepted

Test #10:

score: 5
Accepted
time: 188ms
memory: 24364kb

input:

100000 200000
144608435 -87274600 -974677350 -100352489 -649030362 -39453096 289447879 -537852584 -94574777 337360089 -199669378 -850160928 -298263608 -591161493 231532575 -573617469 -439297426 260642811 425094445 300764130 -476717856 -965323290 102381102 113958066 -683059518 -390842776 -444568945 -...

output:

1949383025
2089788051
2217473154
2317971860
2217473154
2217473154
2109029972
1313420784
2317971860
2217473154
2317971860
2109029972
2317971860
2317971860
2080688479
2317971860
1572475396
2317971860
2109029972
2217473154
2089788051
2317971860
2109029972
1947887794
2109029972
1969937655
2317971860
210...

result:

ok 100024 lines

Subtask #9:

score: 5
Accepted

Test #11:

score: 5
Accepted
time: 189ms
memory: 24336kb

input:

100000 200000
21871390 -860420857 -462213415 -669025807 -260713612 225198084 387180573 31901468 -79466646 -251439643 -593680453 -56298015 -436840232 -277416623 -606833369 311445607 -468196483 -819533304 417838981 -448959219 -517533939 -295117724 -255342449 -218817100 264166786 258541865 7382813 -268...

output:

1689797409
2687069651
2019825451
1806609143
2019825451
3385030765
3385030765
2687069651
3385030765
2758502704
3385030765
3385030765
3385030765
2019825451
2758502704
3385030765
3385030765
2758502704
3385030765
2185444656
2758502704
3385030765
2687069651
3385030765
3385030765
3385030765
3385030765
338...

result:

ok 100081 lines

Test #12:

score: 0
Accepted
time: 194ms
memory: 24428kb

input:

100000 200000
-401401250 -885857116 410723463 -244305377 -25591488 407803305 219938653 -783240987 -225715768 218449074 -899907600 -151354935 -308711466 -10853978 -65937459 86760080 -451157162 -268769676 -510520098 -776019619 -571358783 -152612168 56347434 -532914379 -128957552 -514831396 282407029 4...

output:

2186441814
2362563927
1717698691
2362563927
2362563927
2187267852
2464889211
2325212535
2187267852
2362563927
1561958126
2362563927
1830826681
2362563927
2362563927
2186441814
1999929173
2325212535
1904167572
2325212535
2464889211
2325212535
2362563927
1906990190
2362563927
2362563927
2378323268
236...

result:

ok 100332 lines

Subtask #10:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 202ms
memory: 24344kb

input:

95517 191795
-725239261 -299498656 71286270 -594521669 192006852 271302895 182213759 -447983665 496646313 364428830 141890698 -582020559 102214817 -223415363 -502837969 -762043847 -607694704 -229708001 6321315 240383244 -776743439 193648400 -974528015 44096904 -785689867 -185689539 -492379003 289140...

output:

2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
2554548427
70139131164484
70139131164484
70139131164484
70139131164484
70139131164484
70139131164484
70139131164484
70139131164484
70139131164484
...

result:

wrong answer 5th lines differ - expected: '2571377320', found: '2554548427'

Subtask #11:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 180ms
memory: 24484kb

input:

100000 200000
135797954 -138947496 -406182714 438477901 -267057521 -232444211 130630377 -317348655 37833748 -981372450 246923545 -803068401 216077120 233292050 -267523089 -630927369 -922280156 302142108 -175654796 -464364140 -534375053 -118878135 445980692 -371294038 -797139239 -631637350 418273018 ...

output:

3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
3220264508
322...

result:

wrong answer 198th lines differ - expected: '54316057079819', found: '54316049429589'

Subtask #12:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 194ms
memory: 24320kb

input:

100000 200000
-924767382 -769781514 144232383 -995460305 274241911 -591199999 -462371403 -736028436 -723144279 204535592 -76117810 136712480 197266266 301370706 -157194236 -533948187 439155758 458743159 -856515801 -189489725 -57278555 -20198384 445455871 272093273 -231072195 212372946 245905921 7066...

output:

2749251676
2749251676
2749251676
2555874852
2555874852
2555874852
2555874852
2555874852
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
5462609335899
54...

result:

wrong answer 4th lines differ - expected: '2749251676', found: '2555874852'

Subtask #13:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 169ms
memory: 24360kb

input:

100000 200000
388142692 -345061796 393830628 210472351 75607734 -959422668 -800026188 -960077632 -668437004 -754515329 -307441856 192254236 -451503349 -536240240 376753194 131296191 -966349165 -144012934 -795609529 -4772916 -149566306 -97856138 -913369907 -924695033 20622624 -474639442 283572561 -95...

output:

3110564098
3110564098
3110564098
3110564098
3110564098
3110564098
3110564098
3110564098
3110564098
3110564098
3110564098
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608
19251662950608...

result:

wrong answer 113th lines differ - expected: '52024264472825', found: '52023575741705'

Subtask #14:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 169ms
memory: 24452kb

input:

93028 91818
-295735337 -564744068 -902605531 62391852 -365321307 -603557247 -717081598 162329592 -971363607 247538774 -216804827 -289183462 -770010287 -248152826 -606594806 -23136252 -879560984 -602010879 93750090 -229236489 -647166389 -320819399 -527809250 -999279828 -143001985 -227646820 -49727247...

output:

1903996022
2730626954
2730626954
2730626954
2730626954
2730626954
2730626954
2514281855
2435627856
1675159444
2730626954
2136750003
2488717432
2730626954
2488717432
283119864
2730626954
2730626954
1903996022
2315836813
2488717432
2488717432
6681582669844
1688473585
2488717432
1886524634
584477738820...

result:

wrong answer 15th lines differ - expected: '2514281855', found: '2488717432'

Subtask #15:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 139ms
memory: 24404kb

input:

91507 95839
-23664684 -962845837 -26368215 326675641 -724479 499137961 -879329828 -484112881 -891925211 -24962093 291998659 -444033146 -469035647 215328625 78544430 235825511 -873452291 367590693 -588338012 -64562533 243308218 -90161552 107801329 -540773420 -957858728 -963156371 456254393 -455576987...

output:

1784552270
3394268345
2175108698
3394268345
1814690454
2020894702
2020894702
2175108698
2175108698
2175108698
2020894702
2175108698
2044820932
1814690454
2012110730
2175108698
2175108698
2175108698
2569648408
2175108698
2175108698
2175108698
1941396248
2175108698
2044820932
1814690454
1576029249
205...

result:

wrong answer 5th lines differ - expected: '2087565982', found: '1814690454'

Subtask #16:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 248ms
memory: 24428kb

input:

94402 181505
-575507596 154582735 -580773807 -76942222 -218416229 -420520457 -603882856 -579269638 -968806749 -330938819 -594039411 -853624581 12356239 -335972976 -715519332 -115758740 -139424484 145442017 -586731895 -524655417 62044280 447562515 112543550 286412994 -755863775 -964258126 258612618 -...

output:

2069616963
1493677229
1897346487
1417323687
2075358472
1417323687
2717536602
2717536602
2717536602
27584470137384
2717536602
18602204752657
8960520101050
1555911351
9125185095250
21683479890749
25787635858348
7202840300801
27581231099679
27581231099679
6097938189719
685555259186
4372404479324
110023...

result:

wrong answer 1st lines differ - expected: '2156322198', found: '2069616963'

Subtask #17:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 263ms
memory: 24420kb

input:

97097 197748
-39532660 72924140 -860212972 266724148 -102927196 -536320064 -542895316 -6951259 -451165977 -563012023 -878017150 234956088 -821084308 70082632 103670556 -550194976 5890742 -374521897 -291211030 -189582599 -532780350 153646292 481408375 -522692696 4914802 144236997 -554911116 209552098...

output:

2374171709
2152295655
2768383124
2768383124
2255223694
2255223694
2451052463
1517587897
2152295655
1785752114
2768383124
2768383124
2768383124
2768383124
2768383124
2768383124
2773590811
2136488417
2070174613
1947879088
1947879088
1182355086703
392480261573
1920657260
2242459881
1849117227563
307380...

result:

wrong answer 3rd lines differ - expected: '2773590811', found: '2768383124'

Subtask #18:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 284ms
memory: 24360kb

input:

100000 200000
124057764 -95019391 -978000572 221124832 352671144 -189215640 -621389420 -576096799 -860592121 282165011 443560050 4236897 -184072665 -157472860 451941374 -94913773 -40873747 6340470 -178064909 7793037 -811205774 260938388 129013318 -867099913 -258095930 110791678 139837296 -88254587 -...

output:

2850239691
1721346319
2152894836
2375061287
2679459632
2679459632
1721346319
2679459632
2679459632
2003073076
2679459632
2003073076
2679459632
2375061287
2003073076
1119397859203
2165451423693
836757041418
1452245368471
2165451423693
933050792807
1122697797815
42372866911
2051516615745
360303043882
...

result:

wrong answer 4th lines differ - expected: '2850239691', found: '2375061287'

Subtask #19:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 253ms
memory: 24404kb

input:

100000 200000
-613945542 -776631594 -426750433 204865476 -956716144 289199620 -415317595 -88687071 -31304858 341801980 -657704863 -153593964 -334118199 -544077510 -801376065 -371865322 -829707245 -144589260 -231246860 -393207796 -260603663 195684150 118550317 -165300622 -770784867 -315971863 -518967...

output:

3010106070
1721382511
2080111992
1721038508967
244905851072
3010106070
3010106070
125824464105
765746312629
649827265
1396525995037
301269647632
3010106070
1518554836565
3010106070
3010106070
226509243499
1073556391056
1312679496260
2080111992
1245016746743
1919654476
645552736978
1715876634995
7488...

result:

wrong answer 4th lines differ - expected: '1721780219697', found: '1721038508967'

Subtask #20:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 290ms
memory: 24424kb

input:

100000 200000
-839752687 193465364 -320699181 364320507 491503148 58174453 -204127703 -818328812 -374166865 -186497314 -99589760 355057503 107437758 101726988 341975032 -881462802 272573187 -493611511 27393952 60635930 94215380 64708383 -472618291 -712265364 -520878214 -426679966 347269993 52124326 ...

output:

1982457074
2200495086
2149209979
2290312575
2290312575
2678047382
131667427553
1969960056
240545314467
250739080681
417961671940
1247489149
2678047382
2380156438
7075091015
134755646490
427623083754
2237836949
233151197269
72785108220
2080852682638
98844802387
4842595205434
4161963842978
28891704480...

result:

wrong answer 7th lines differ - expected: '131719771584', found: '131667427553'