QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149418#4409. 袜子zhouershan15 6909ms472496kbC++2020.6kb2023-08-24 16:10:442023-08-24 16:10:46

Judging History

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

  • [2023-08-24 16:10:46]
  • 评测
  • 测评结果:15
  • 用时:6909ms
  • 内存:472496kb
  • [2023-08-24 16:10:44]
  • 提交

answer

// #define LOCAL
// #define DEBUG
// #define DEBUG__
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) {
    x = min(x, y);
}
template <typename T>
inline void chkmax(T &x, T y) {
    x = max(x, y);
}
namespace FastIO {
// ------------------------------
#define IN_HAS_NEG
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr,
                                               *_read_ptr_end = nullptr;
inline char gc() {
    if (__builtin_expect(_read_ptr == _read_ptr_end, false)) {
        _read_ptr = _read_buffer;
        _read_ptr_end =
            _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
        if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;
#endif
    }
    return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr =
    (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c) {
    *_write_ptr++ = c;
    if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) {
        fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
        _write_ptr = _write_buffer;
    }
}
INLINE_V struct _auto_flush {
    ~_auto_flush() {
        fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
    }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline bool _isdigit(char c) { return (c & 16) && c != EOF; }
inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline bool _isdigit(char c) { return c & 16; }
inline bool _isgraph(char c) { return c > 32; }
#endif
template <class T>
INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <class T>
INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed;
template <class T>
INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <>
INLINE_V constexpr bool _is_integer<__int128> = true;
template <>
INLINE_V constexpr bool _is_integer<__uint128_t> = true;
template <>
INLINE_V constexpr bool _is_signed<__int128> = true;
template <>
INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
#undef INLINE_V
inline void read(char &c) {
    do c = gc();
    while (!_isgraph(c));
}
inline void read_cstr(char *s) {
    char c = gc();
    while (!_isgraph(c)) c = gc();
    while (_isgraph(c)) *s++ = c, c = gc();
    *s = 0;
}
inline void read(string &s) {
    char c = gc();
    s.clear();
    while (!_isgraph(c)) c = gc();
    while (_isgraph(c)) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template <class T, enable_if_t<_is_signed<T>, int> = 0>
inline void read(T &x) {
    char c = gc();
    bool f = true;
    x = 0;
    while (!_isdigit(c)) {
        if (c == 45) f = false;
        c = gc();
    }
    if (f)
        while (_isdigit(c)) x = x * 10 + (c & 15), c = gc();
    else
        while (_isdigit(c)) x = x * 10 - (c & 15), c = gc();
}
template <class T, enable_if_t<_is_unsigned<T>, int> = 0>
#else
template <class T, enable_if_t<_is_integer<T>, int> = 0>
#endif
inline void read(T &x) {
    char c = gc();
    while (!_isdigit(c)) c = gc();
    x = 0;
    while (_isdigit(c)) x = x * 10 + (c & 15), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) {
    while (*s) pc(*s++);
}
inline void write(const string &s) {
    for (char c : s) pc(c);
}
#ifdef OUT_HAS_NEG
template <class T, enable_if_t<_is_signed<T>, int> = 0>
inline void write(T x) {
    char buffer[numeric_limits<T>::digits10 + 1];
    int digits = 0;
    if (x >= 0) do
            buffer[digits++] = (x % 10) | 48, x /= 10;
        while (x);
    else {
        pc(45);
        do buffer[digits++] = -(x % 10) | 48, x /= 10;
        while (x);
    }
    while (digits) pc(buffer[--digits]);
}
template <class T, enable_if_t<_is_unsigned<T>, int> = 0>
#else
template <class T, enable_if_t<_is_integer<T>, int> = 0>
#endif
inline void write(T x) {
    char buffer[numeric_limits<T>::digits10 + 1];
    int digits = 0;
    do buffer[digits++] = (x % 10) | 48, x /= 10;
    while (x);
    while (digits) pc(buffer[--digits]);
}
template <int N>
struct _tuple_io_helper {
    template <class... T>
    static inline void _read(tuple<T...> &x) {
        _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x));
    }
    template <class... T>
    static inline void _write(const tuple<T...> &x) {
        _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x));
    }
};
template <>
struct _tuple_io_helper<1> {
    template <class... T>
    static inline void _read(tuple<T...> &x) {
        read(get<0>(x));
    }
    template <class... T>
    static inline void _write(const tuple<T...> &x) {
        write(get<0>(x));
    }
};
template <class... T>
inline void read(tuple<T...> &x) {
    _tuple_io_helper<sizeof...(T)>::_read(x);
}
template <class... T>
inline void write(const tuple<T...> &x) {
    _tuple_io_helper<sizeof...(T)>::_write(x);
}
template <class T1, class T2>
inline void read(pair<T1, T2> &x) {
    read(x.first), read(x.second);
}
template <class T1, class T2>
inline void write(const pair<T1, T2> &x) {
    write(x.first), pc(32), write(x.second);
}
template <class T1, class... T2>
inline void read(T1 &x, T2 &...y) {
    read(x), read(y...);
}
template <class... T>
inline void read_cstr(char *x, T *...y) {
    read_cstr(x), read_cstr(y...);
}
template <class T1, class... T2>
inline void write(const T1 &x, const T2 &...y) {
    write(x), write(y...);
}
template <class... T>
inline void write_cstr(const char *x, const T *...y) {
    write_cstr(x), write_cstr(y...);
}
template <class T>
inline void print(const T &x) {
    write(x);
}
inline void print_cstr(const char *x) { write_cstr(x); }
template <class T1, class... T2>
inline void print(const T1 &x, const T2 &...y) {
    print(x), pc(32), print(y...);
}
template <class... T>
inline void print_cstr(const char *x, const T *...y) {
    print_cstr(x), print_cstr(y...);
}
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template <class... T>
inline void println(const T &...x) {
    print(x...), pc(10);
}
template <class... T>
inline void println_cstr(const T *...x) {
    print_cstr(x...), pc(10);
}
}  // namespace FastIO
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
    T y;
    swap(x, y);
}
const int N = 5e4 + 10, M = 5e5 + 10;
int n, m;
ll col[N];
ll finalans[M];
namespace DATA {
struct Frac {
    ll x, y;
    inline Frac(ll _x, ll _y) {
        x = _x, y = _y;
        if (y < 0) x = -x, y = -y;
        assert(_y);
    }
    inline Frac() { x = 0, y = 1; }
    inline bool operator<(Frac b) const { return x * b.y < b.x * y; }
    inline bool operator<=(Frac b) const { return x * b.y <= b.x * y; }

    inline bool operator>(Frac b) const { return x * b.y > b.x * y; }
    inline bool operator==(Frac b) const { return x * b.y == b.x * y; }
    inline bool operator!=(Frac b) const { return x * b.y != b.x * y; }
};
struct Point {
    ll x, y;
    int col;
};
struct Querya {
    ll a, b, c;
    int id;
    inline bool operator<(Querya _) const { return id < _.id; }
    inline bool countain(Point r) { return -r.x * a + r.y * b + c < 0; }
};
};  // namespace DATA
using namespace DATA;
Point a[N];
double T_sum, T_sum2;
ll nans = 0;
// task
namespace WATER_SCANLINE {
vector<Querya> q;
inline void solve() {
    vector<Querya> x;
    for (auto _ : q)
        if (_.a > 0) x.emplace_back(_);
    sort(x.begin(), x.end(), [&](Querya x, Querya y) {
        return Frac{-x.c, x.a} < Frac{-y.c, y.a};
    });
    sort(a + 1, a + n + 1, [&](Point x, Point y) { return x.x < y.x; });
    int r = 1;
    memset(col, 0, sizeof(col)), nans = 0;
    for (auto [aa, b, c, id] : x) {
        while (r <= n && Frac{a[r].x, 1} < Frac{-c, aa}) {
            int c = a[r].col;
            nans -= 1ll * col[c] * col[c], ++col[a[r].col];
            nans += 1ll * col[c] * col[c], ++r;
        }
        finalans[id] = nans;
    }
    memset(col, 0, sizeof(col)), nans = 0, clear(x);
    for (auto _ : q)
        if (_.a < 0) x.emplace_back(_);
    sort(x.begin(), x.end(), [&](Querya x, Querya y) {
        return Frac{x.c, -x.a} > Frac{y.c, -y.a};
    });
    sort(a + 1, a + n + 1, [&](Point x, Point y) { return x.x > y.x; }), r = 1;
    for (auto [aa, b, c, id] : x) {
        while (r <= n && Frac{a[r].x, 1} > Frac{-c, aa}) {
            int c = a[r].col;
            nans -= 1ll * col[c] * col[c], ++col[a[r++].col];
            nans += 1ll * col[c] * col[c];
        }
        finalans[id] = nans;
    }
}
};  // namespace WATER_SCANLINE
namespace SHU_SCANLINE {
vector<Querya> q;
inline void solve() {
    vector<Querya> x;
    for (auto _ : q)
        if (_.b > 0) x.emplace_back(_);
    sort(x.begin(), x.end(), [&](Querya x, Querya y) {
        return Frac{-x.c, x.b} < Frac{-y.c, y.b};
    });
    sort(a + 1, a + n + 1, [&](Point x, Point y) { return x.y < y.y; });
    int r = 1;
    memset(col, 0, sizeof(col)), nans = 0;
    for (auto [aa, b, c, id] : x) {
        while (r <= n && Frac{a[r].y, 1} < Frac{-c, b}) {
            int c = a[r].col;
            nans -= 1ll * col[c] * col[c], ++col[a[r++].col];
            nans += 1ll * col[c] * col[c];
        }
        finalans[id] = nans;
    }
    memset(col, 0, sizeof(col)), nans = 0, clear(x);
    for (auto _ : q)
        if (_.b < 0) x.emplace_back(_);
    sort(x.begin(), x.end(), [&](Querya x, Querya y) {
        return Frac{-x.c, x.b} > Frac{-y.c, y.b};
    });
    sort(a + 1, a + n + 1, [&](Point x, Point y) { return x.y > y.y; }), r = 1;
    for (auto [aa, b, c, id] : x) {
        while (r <= n && Frac{a[r].y, 1} > Frac{-c, b}) {
            int c = a[r].col;
            nans -= 1ll * col[c] * col[c], ++col[a[r++].col];
            nans += 1ll * col[c] * col[c];
        }
        finalans[id] = nans;
    }
}
};  // namespace SHU_SCANLINE
namespace MOQUE {
template <const int S, const int L, typename T>
struct darry {
    pair<int, T> a[S];
    T chi[S];
    T *top[L], *nt;
    int sz[L], len;
    struct vector_helper {
        darry &arr;
        int posx;
        inline T *begin() { return arr.top[posx]; }
        inline T *end() { return arr.top[posx] + arr.sz[posx]; }
        inline void push(T x) { arr.a[++arr.len] = {posx, x}; }
    };
    inline void clear() { len = 0; }
    inline void build() {
        nt = chi, memset(sz, 0, sizeof(sz));
        for (int i = 1; i <= len; i++) ++sz[a[i].first];
        for (int i = 0; i < L; i++) top[i] = nt, nt += sz[i], sz[i] = 0;
        for (int i = 1; i <= len; i++)
            top[a[i].first][sz[a[i].first]++] = a[i].second;
    }
    inline vector_helper operator[](int x) { return {*this, x}; }
};
// vector<pair<int, int> >
darry<33000000, 500005, int> vec;
struct Queryb {
    double k;
    ll A, B, S, T;
    int id;
    inline bool countain1(Point x) { return -A * x.x + B * x.y + S < 0; }
    inline bool countain2(Point x) { return -A * x.x + B * x.y + T < 0; }
    inline bool countain1_(Point x) { return A * x.x + B * x.y + S < 0; }
    inline bool countain2_(Point x) { return A * x.x + B * x.y + T < 0; }
    inline bool operator<(Queryb y) const { return k < y.k; }
};
vector<Queryb> f, f2;
vector<Querya> q;
vector<pair<Frac, Querya> > task[N], task2[N];
mt19937 rng(random_device{}());
pair<int, Point> b1[N], b2[N], b3[N], b4[N];
inline bool cmp1(Point x, Point y) {
    return x.x != y.x ? x.x < y.x : x.y < y.y;
}
inline bool cmp2(Point x, Point y) {
    return x.x != y.x ? x.x > y.x : x.y > y.y;
}
const int S = 1005;
struct Update {
    int x, y;
    double k;
    inline bool operator<(Update b) const { return k < b.k; }
} c[S * S], c2[S * S];
int pos1[N], pos2[N], pos3[N], pos4[N], id[N];
vector<int> vec2[N];
inline void update1(pair<int, Point> *b, int *pos, int u, int v) {
    if (pos[u] > pos[v]) return;
    while (pos[u] < pos[v]) {
        int nv = b[pos[u] + 1].first;
        swap(b[pos[u]], b[pos[nv]]), swap(pos[u], pos[nv]);
        u = nv;
    }
}
inline int upper(pair<int, Point> *b, Querya x, int sz) {
    if (x.countain(b[sz].second)) return sz + 1;
    int ans = sz + 1;
    int L = 1, R = sz, mid;
    while (L <= R) {
        mid = L + R >> 1;
        if (x.countain(b[mid].second))
            L = mid + 1;
        else
            ans = mid, R = mid - 1;
    }
    return ans;
}
inline void solve(int x) {
    double pre = clock();
    for (int i = 1; i <= x; i++)
        b1[i].second.x = -b1[i].second.x, b2[i] = b1[i];
    int len = 0;
    sort(b1 + 1, b1 + x + 1, [&](pair<int, Point> a, pair<int, Point> b) {
        return cmp1(a.second, b.second);
    });
    sort(b2 + 1, b2 + x + 1, [&](pair<int, Point> a, pair<int, Point> b) {
        return cmp2(a.second, b.second);
    });
    for (int i = 1; i <= x; i++)
        for (int j = i + 1; j <= x; j++)
            if (b1[i].second.x != b1[j].second.x) {
                double t = double(b1[i].second.y - b1[j].second.y) /
                           (b1[i].second.x - b1[j].second.x);
                if (t < f.back().k) c[++len] = {i, j, t};
            }
    sort(c + 1, c + len + 1);
    T_sum += clock() - pre;
    for (int i = 1; i <= x; i++)
        pos2[i] = pos1[i] = i, b2[i].first = b1[i].first = i;
    int r = 1, r2 = 1;
    double pre2 = clock();
    for (auto s : f) {
        auto [k, A, B, S, T, id] = s;
        while (r <= len && c[r].k < k) {
            update1(b1, pos1, c[r].x, c[r].y),
                update1(b2, pos2, x - c[r].y + 1, x - c[r].x + 1), ++r;
        }
        if (B > 0) {
            int aa = upper(b1, {A, B, S}, x), bb = upper(b1, {A, B, T}, x);
            if (aa > bb) swap(aa, bb);
            for (int i = aa; i < bb; i++)
                if (s.countain1(b1[i].second) && !s.countain2(b1[i].second))
                    vec[id].push(b1[i].second.col);
                else if (!s.countain1(b1[i].second) &&
                         s.countain2(b1[i].second))
                    vec[id].push(-b1[i].second.col);
        } else {
            int aa = upper(b2, {A, B, S}, x), bb = upper(b2, {A, B, T}, x);
            if (aa > bb) swap(aa, bb);
            for (int i = aa; i < bb; i++)
                if (s.countain1(b2[i].second) && !s.countain2(b2[i].second))
                    vec[id].push(b2[i].second.col);
                else if (!s.countain1(b2[i].second) &&
                         s.countain2(b2[i].second))
                    vec[id].push(-b2[i].second.col);
        }
    }
    T_sum2 += clock() - pre;
}
inline void count(bool flag) {
    int s = max(1, int(sqrt(f.size() * 0.6)));
    if (flag)
        for (auto &[k, A, B, S, T, id] : f) A = -A;
    for (int i = 1; i <= n; i += s) {
        for (int j = i; j < min(n + 1, i + s); j++) b1[j - i + 1].second = a[j];
        if (flag) {
            for (int j = i; j < min(n + 1, i + s); j++)
                b1[j - i + 1].second.x = -b1[j - i + 1].second.x;
        }
        solve(min(n - i + 1, s));
    }
}
inline void add(int x) {
    nans -= col[x] * col[x], ++col[x], nans += col[x] * col[x];
}
inline void del(int x) {
    nans -= col[x] * col[x], --col[x], nans += col[x] * col[x];
}
Point p[N];
vector<Point> fa, fb;
vector<int> veca[N], vecb[N];
inline int upper2(Point x, int u) {
    if (!task[u].size()) return 0;
    if (!(Frac(x.x, x.y) < task[u].back().first)) return task[u].size();
    int L = 0, R = task[u].size() - 1, M, ans = task[u].size();
    while (L <= R) {
        M = L + R >> 1;
        if (Frac(x.x, x.y) < task[u][M].first)
            ans = M, R = M - 1;
        else
            L = M + 1;
    }
    return ans;
}
inline int lower2(Point x, int u) {
    if (!task[u].size()) return 0;
    if (!(Frac(x.x, x.y) <= task[u].back().first)) return task[u].size();
    int L = 0, R = task[u].size() - 1, M, ans = task[u].size();
    while (L <= R) {
        M = L + R >> 1;
        if (Frac(x.x, x.y) <= task[u][M].first)
            ans = M, R = M - 1;
        else
            L = M + 1;
    }
    return ans;
}
Point b[N];
namespace Rotate_Scanline {
inline void rotate_scanline(int u, bool fl) {
    if (!task[u].size()) return;
    memset(col, 0, sizeof(col)), nans = 0;
    for (int i = 0; i <= task[u].size(); i++) clear(veca[i]), clear(vecb[i]);
    sort(task[u].begin(), task[u].end());
    for (int i = 1; i <= n; i++) {
        b[i] = {a[i].x - p[u].x, a[i].y - p[u].y, a[i].col};
        if (fl) b[i].x = -b[i].x;
        if (b[i].y == 0) {
            if (b[i].x < 0) add(b[i].col);
        } else if (b[i].y < 0)
            veca[lower2(b[i], u)].push_back(b[i].col), add(b[i].col);
        else
            vecb[upper2(b[i], u)].push_back(b[i].col);
    }
    for (int i = 0; i < task[u].size(); i++) {
        auto [k, s] = task[u][i];
        for (int v : vecb[i]) add(v);
        for (int v : veca[i]) del(v);
        for (int v : vec[s.id]) (v < 0 ? del : add)(abs(v));
        ::finalans[s.id] = nans;
        for (int v : vec[s.id]) (v < 0 ? add : del)(abs(v));
    }
}
};  // namespace Rotate_Scanline
using namespace Rotate_Scanline;
inline int getrand() { return rng() % 3 + -1; }
inline void solve() {
    if (!q.size()) return;
    int s = max(1, int(sqrt(q.size() * 0.65)));
    shuffle(a + 1, a + n + 1, rng);
    clear(f), vec.clear();
    for (int i = 1; i <= s; i++) clear(task[i]);
    for (int i = 1; i <= s; i++)
        p[i] = {a[i].x + getrand(), a[i].y + getrand()};
    for (auto v : q) {
        ll nans = LLONG_MAX, nansid = 0;
        for (int j = 1; j <= s; j++) {
            ll pos = (1ll * p[j].x * v.a + 1ll * p[j].y * v.b + v.c);
            if (abs(pos) < abs(nans)) nans = pos, nansid = j;
        }
        Queryb x = {abs(double(v.a) / (v.b)), v.a, v.b, v.c, v.c - nans, v.id};
        if (v.a > 0)
            task[nansid].emplace_back(Frac{-v.b, abs(v.a)}, v);
        else
            task2[nansid].emplace_back(Frac{-v.b, abs(v.a)}, v);

#ifdef DEBUG__
        for (int i = 1; i <= n; i++)
            if (x.countain1_(a[i]) && !x.countain2_(a[i]))
                vec2[v.id].push_back(a[i].col);
            else if (x.countain2_(a[i]) && !x.countain1_(a[i]))
                vec2[v.id].push_back(-a[i].col);
#endif
        if (v.a * v.b > 0)
            f.push_back(x);
        else
            f2.push_back(x);
    }
    sort(f.begin(), f.end());
    sort(f2.begin(), f2.end());
    count(0), f = f2, count(1);
    vec.build();
    for (int i = 1; i <= s; i++)
        rotate_scanline(i, 0), task[i] = task2[i], rotate_scanline(i, 1);
#ifdef DEBUG__
    cout << "m:" << m << endl;
    for (int i = 1; i <= m; i++) {
        cout << "-" << endl;
        for (int v : vec[i]) cout << v << ' ';
        cout << endl;
        for (int v : vec2[i]) cout << v << ' ';
        cout << endl << endl;
    }
#endif
}
};  // namespace MOQUE
namespace PREV {
vector<Querya> q;
inline void solve() {
    MOQUE::q = q, MOQUE::solve();
    clear(MOQUE::q);
}
};  // namespace PREV
namespace READ {
Querya q[M];
inline void init() {
    read(n, m);
    for (int i = 1; i <= n; i++) read(a[i].x, a[i].y, a[i].col);
    for (int i = 1; i <= m; i++) {
        read(q[i].a, q[i].b, q[i].c), q[i].id = i;
        if (!q[i].a)
            SHU_SCANLINE::q.push_back(q[i]);
        else if (!q[i].b)
            WATER_SCANLINE::q.push_back(q[i]);
        else
            PREV::q.push_back(q[i]);
    }
}
};  // namespace READ
int main() {
    READ::init();
    SHU_SCANLINE::solve(), WATER_SCANLINE::solve();
    // MOQUE::solve();
    PREV::solve();
    for (int i = 1; i <= m; i++) println(finalans[i]);
    cerr << double(clock()) / CLOCKS_PER_SEC << ' ' << T_sum / CLOCKS_PER_SEC
         << ' ' << T_sum2 / CLOCKS_PER_SEC << endl;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 28ms
memory: 276080kb

input:

1000 1000
8756 4483 237
-7891 -2818 114
8667 -7202 36
8150 -2 248
-4483 -9934 375
-9669 -1815 802
4008 9788 22
-2193 -4988 307
-9813 -4926 22
6344 8542 93
-9906 -9906 38
-3791 -2822 814
-7118 8408 51
-779 9589 3
-3211 1342 73
2346 -6502 112
31 -5037 6
3714 -4554 118
8788 6735 533
3860 -4232 5
3257 6...

output:

1047
1034
1001
1061
1060
956
1029
1001
1048
1001
1052
1023
1077
0
1077
1015
1060
1012
1022
1022
1077
1369
993
1001
1060
1003
1077
1034
1063
0
1001
1038
0
1001
1077
1001
1063
1063
1060
1034
0
1060
1060
1077
1031
1021
939
1023
849
1001
1060
1000
1008
1150
1007
878
1060
1060
1020
1043
1045
1077
1048
0
...

result:

ok 1000 numbers

Test #2:

score: 0
Accepted
time: 13ms
memory: 275044kb

input:

1000 1000
-809378 594895 7
-463965 286585 108
492337 -110361 235
163858 -391125 15
-546105 -878318 214
360416 -730538 407
-298417 -177165 227
752631 -788118 51
17699 323971 105
843170 208717 105
766811 396573 69
127415 309072 39
637608 -188063 352
224425 -952868 139
850507 751278 110
-995626 648647 ...

output:

997
969
935
993
9
1023
998
1014
999
969
1001
982
1023
937
1028
1035
973
1029
953
969
25
1001
889
976
985
1023
937
1023
1006
992
937
1009
1023
969
969
1001
925
937
969
1001
969
1023
937
937
1000
1023
969
932
962
1001
969
994
937
1001
937
905
1008
937
1023
958
1023
1001
731
1015
956
988
945
970
1042
9...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 16ms
memory: 275776kb

input:

1000 1000
-329387625 -341019218 102
13965986 806087844 9
-528171131 227425809 15
786487633 15830440 3
539535861 -963497336 7
-742845817 -372626578 35
-787231340 -132749801 3
-543467667 -942295910 119
-672244153 -833463748 15
-641088972 317851104 1
65665573 -823079703 26
247807062 -882007619 11
-6610...

output:

4529
5025
4868
4426
3446
3771
3781
3700
4842
4604
4259
3557
3731
3538
3979
4367
4879
3595
4336
3446
4754
3632
3762
3750
3446
4879
4728
4668
4610
3781
4816
3600
3760
4868
3760
3446
4387
3446
3760
4529
4447
4019
4879
3781
3611
4529
4529
4865
4711
3446
4868
4104
3446
3760
3781
3387
4647
4736
4519
3730
...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 8ms
memory: 274628kb

input:

1000 1000
-240930145 126765047 4
5029224 -538225798 8
748056353 -6881636 1
254300626 659262809 8
590237623 -34857701 1
655683714 -171537454 3
582680000 -835569740 4
-746501072 381914331 1
-696675178 165921148 6
73362513 -665223969 4
-204185218 875019442 5
-656420293 -589534031 5
-326306612 -57437624...

output:

23040
20550
23040
23667
19699
22762
21160
20433
22290
21231
20550
21874
20500
20550
23040
22949
23485
24394
21591
24045
19681
20491
21324
22226
20082
24060
20505
23603
19699
20550
21488
23667
20491
19699
23667
21061
21600
20550
21015
21876
22917
22481
23040
22902
19699
20858
19699
21919
21725
20490
...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 30ms
memory: 275680kb

input:

1000 1000
-886939246 -956433905 4
458364194 -989591596 1
-69057070 -647489199 2
-34535206 -500686466 1
671489436 -224022957 1
-487072455 294047705 4
-284801195 490213612 1
27112031 -736294945 1
-408100248 967227200 4
107685527 147821041 1
-759670783 -778138619 7
554606387 -117974098 2
-543318085 -66...

output:

126533
125819
126518
116416
115569
112523
113786
120221
115569
126703
126174
125954
113560
113560
115569
129937
124149
120150
115569
120801
119337
129285
126174
126174
127311
119240
120252
127733
124149
113560
113560
115569
115936
130657
120313
120798
115569
131931
112735
120197
123145
115569
120234...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 8ms
memory: 274940kb

input:

1000 1000
-140707073 -709357437 276
666979616 294563099 34
507506113 -978340110 245
-41619729 -632363033 28
450190358 -768866476 86
-106476442 -83684337 574
477466216 479545563 220
196637637 -181541675 119
427079800 435777395 406
30465211 86113444 760
129968522 814179371 129
719311691 325225596 48
-...

output:

1003
986
1063
1104
1058
1054
1004
1018
1011
1082
1065
1009
967
1081
1071
964
1014
964
1015
1030
1010
1059
1019
1027
1062
1027
1006
1064
1081
1027
1086
1037
1015
995
1081
1000
1015
1056
1014
1005
966
1024
1095
1003
1012
993
1081
1003
1058
1027
1039
1015
1045
1014
967
1003
1014
959
1047
1006
1014
1082...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 20ms
memory: 274220kb

input:

1000 1000
-447447700 -591263241 63
-216023636 -506993336 886
-723265777 481650149 2
380816011 -971341762 11
-433458798 217059466 113
-649457481 318097209 59
998475552 -512422664 128
-293129715 -964655164 511
-403596696 -668671938 515
-212213731 -448158397 80
-761541201 -739537496 122
-686289475 -803...

output:

914
914
940
960
991
1045
1051
1053
1029
1015
914
1092
961
1051
958
988
1032
1051
1092
961
961
946
1051
1037
961
986
1023
1009
1051
1057
1044
1092
1025
1092
956
914
980
1087
927
1092
1005
1006
969
999
1002
914
914
1041
932
1031
1056
1048
1058
1070
1027
1092
1057
964
1051
961
1051
1064
1062
914
971
10...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 18ms
memory: 274448kb

input:

1000 1000
-541722175 476510525 31
628338000 759271580 381
-271238678 800070438 512
780664157 -680638999 186
-426546737 121982760 93
270959547 -103484346 577
-598325723 -197010965 114
112923702 786079875 121
-519492810 -842104927 16
555941748 784488471 103
-689093484 169597790 85
-164649986 -99979169...

output:

1004
885
1009
950
994
1095
1008
1071
1016
862
958
1009
1095
1054
1007
1007
1095
1007
1082
1095
1095
885
890
1009
913
1042
987
885
885
1071
886
1065
1009
1007
1005
1121
888
1033
918
1074
1051
1042
885
1008
1004
1009
1095
1095
1007
1102
1052
1028
1089
1095
905
890
1027
1095
1095
1129
1007
885
1029
103...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 8ms
memory: 274268kb

input:

1000 1000
223130280 -358540334 70
-446423718 -649264507 25
952545239 -115890499 74
198701646 411091447 52
-543555719 -183987016 671
-138533088 462438454 72
780376261 275581957 624
-269723997 -448427286 73
706578440 987790609 157
-804222735 801819299 503
915059774 569425246 54
-221158650 -190676516 2...

output:

1022
1010
1032
1085
978
1022
927
948
1032
1081
1030
948
1018
980
965
936
1022
1010
1010
1016
942
1030
1030
948
1022
950
1010
1022
1032
948
937
960
1011
1010
1010
1022
1067
1010
1095
1017
980
1070
948
1019
964
1045
1022
1069
1029
1086
1022
1010
948
1010
984
944
1010
1010
949
1030
985
957
943
1028
107...

result:

ok 1000 numbers

Test #10:

score: 0
Accepted
time: 21ms
memory: 274116kb

input:

1000 1000
-580044540 7764137 285
-849966519 -358165808 235
877921194 265967662 564
304785558 62822807 48
116178894 720156161 210
894895305 -213358952 51
655074511 -309026876 195
296310508 -237014578 134
-255019899 626409905 55
-557361321 990535673 287
106143372 -769370053 523
-935285432 -394592511 8...

output:

887
862
1006
824
927
883
1017
1020
1010
909
1022
1006
942
855
1051
912
885
876
873
862
1032
892
883
1032
909
1007
912
862
841
876
1010
1033
912
883
985
862
1006
912
930
912
985
1021
934
1006
808
873
1034
1006
1032
912
862
1030
1000
880
1009
824
1032
894
1092
873
1085
1006
1031
888
937
909
1032
1006
...

result:

ok 1000 numbers

Subtask #2:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 5616ms
memory: 472496kb

input:

50000 500000
384309433 -953786733 1
-381089810 891795502 1
-701194776 440247159 1
-403243027 539105336 1
275206790 -652250203 1
-554746251 903743804 1
-457035253 912757156 1
-342310772 -17612092 1
-440332191 682239316 1
730332275 816145283 1
-701691234 -908289789 1
-632861504 -277378843 1
-567495050...

output:

618496745
614079729
616866497
614478068
613189405
616715138
615126465
616114802
614529490
614077984
616764805
614626805
615475280
615176840
617956645
618705730
613485153
614626805
614626805
612802541
617062849
617662305
613684025
618496745
612900340
615420738
613682609
617857600
616568900
614626805
...

result:

ok 500000 numbers

Test #12:

score: 0
Accepted
time: 6909ms
memory: 467040kb

input:

50000 500000
729905 -125985 1
926315 959640 1
123096 -91945 1
-186481 965101 1
-425756 271410 1
-158109 -800982 1
122987 441100 2
-732281 918630 1
182284 -51080 1
-380410 -929492 1
472062 848544 1
671209 376870 1
366165 -263178 1
-539467 -62456 1
942084 68081 1
384749 792849 1
-648204 -741411 2
7878...

output:

398628245
392170825
389391829
388440685
392182688
387805108
381517693
384525010
390830690
397720525
391054036
392346085
516745745
395682701
395754553
388205365
395821634
398565154
1051363802
385964164
387885617
390926962
22605145
389138933
386438306
387558676
390944065
392346085
398628245
391344637
...

result:

ok 500000 numbers

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #13:

score: 0
Time Limit Exceeded

input:

50000 500000
-9418 -1818 20
7456 -4051 11
2408 1036 12
9188 -5797 26
-2810 -6058 10
-1870 -5476 15
-4838 3308 10
-7573 -547 12
-8221 -6779 58
4436 -6839 78
-5131 -5558 31
-636 7994 15
3144 8637 2
-9161 -7142 63
-5699 -3454 72
-5585 3911 7
6193 -8685 68
6768 1154 37
-5097 -5253 9
7322 6256 8
-4366 71...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #19:

score: 0
Time Limit Exceeded

input:

50000 500000
2598 -1000000 6
1388 -1000000 3
5492 1000000 8
-1000000 -3573 23
-1000000 -7880 15
-4285 1000000 7
1000000 5211 5
-1000000 5915 79
7147 -1000000 29
-9495 -1000000 25
9028 1000000 1
1000000 -4880 20
-8498 1000000 53
1000000 -4256 22
3107 -1000000 29
2061 -1000000 45
8876 -1000000 76
-279...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #25:

score: 0
Time Limit Exceeded

input:

50000 500000
407 -5105 53
6211 98 81
7444 6196 1
-4294 -9353 26
4316 -3143 1
7144 2361 17
6364 -2245 14
-8684 -6564 3
6269 -687 2
-3139 5693 12
-9991 6547 20
2179 2178 47
-6588 7830 21
-6216 -200 3
9207 8834 24
9388 -5953 31
7752 4125 39
7875 -5517 22
-4701 2244 12
8088 3158 4
-4446 3467 1
-1002 154...

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #31:

score: 0
Time Limit Exceeded

input:

20000 200000
6638 9179 76
-6000 442 3
3879 -6574 7
8687 4572 8
3147 5179 38
253 -9723 3
-7740 -1232 4
-3694 -5085 2
404 8299 31
-7760 -1678 9
-1545 2578 10
-1619 -3470 60
8213 5421 30
3532 -3882 33
-7243 -4051 16
8061 7004 47
-1210 -2676 7
466 1969 20
4548 1421 34
-7818 -6690 5
-4934 -9618 1
-2580 -...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%