Submission #695094

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695094	2023-02-04T17:37:59 Z	Nhoksocqt1	Relativnost (COCI15_relativnost)	C++17	140 / 140	2445 ms	24076 KB

relativnost

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}

	if(ch == '-') minus = true; else result = ch - '0';
	while(true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}

	if(minus)
		return -result;
	else
		return result;
}

const int MAXN = 100005;
const int modl = 10007;

struct Node {
    int a, b;
    short f[21];

    Node() {
        memset(f, 0, sizeof(f));
        a = b = 0;
    }

} seg[4 * MAXN];

int a[MAXN], b[MAXN], nArr, numQuery, C;

inline void add(short &a, const short &b) {
    if((a += b) >= modl)
        a -= modl;
}

void mergeNode(Node &res, const Node &a, const Node &b) {
    for (int i = 0; i <= C; ++i)
        res.f[i] = 0;

    for (int i = 0; i <= C; ++i) {
        for (int j = 0; j <= C; ++j) {
            add(res.f[min(i + j, C)], int(a.f[i]) * b.f[j] % modl);
        }
    }
}

void build(int id, int l, int r) {
    if(l == r) {
        seg[id].f[0] = b[l], seg[id].f[1] = a[l];
        seg[id].a = a[l], seg[id].b = b[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    mergeNode(seg[id], seg[id << 1], seg[id << 1 | 1]);
}

void update(int pos, int a, int b) {
    int id(1), l(1), r(nArr);
    while(l != r) {
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            id <<= 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }
    }

    seg[id].f[0] = b, seg[id].f[1] = a;
    seg[id].a = a, seg[id].b = b;
    while(id > 1) {
        id >>= 1;
        mergeNode(seg[id], seg[id << 1], seg[id << 1 | 1]);
    }
}

void process() {
    cin >> nArr >> C;
    for (int i = 1; i <= nArr; ++i) {
        cin >> a[i];
        a[i] %= modl;
    }

    for (int i = 1; i <= nArr; ++i) {
        cin >> b[i];
        b[i] %= modl;
    }

    build(1, 1, nArr);

    cin >> numQuery;
    for (int t = 0; t < numQuery; ++t) {
        int pos, a, b;
        cin >> pos >> a >> b;
        update(pos, a % modl, b % modl);
        cout << seg[1].f[C] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("relativnost.inp", "r", stdin);
//    freopen("relativnost.out", "w", stdout);

    process();
    return 0;
}

Compilation message

relativnost.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
relativnost.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	20696 KB	Output is correct
2	Correct	21 ms	20692 KB	Output is correct
3	Correct	34 ms	20696 KB	Output is correct
4	Correct	424 ms	23516 KB	Output is correct
5	Correct	1163 ms	23908 KB	Output is correct
6	Correct	1862 ms	23784 KB	Output is correct
7	Correct	683 ms	23612 KB	Output is correct
8	Correct	368 ms	23592 KB	Output is correct
9	Correct	653 ms	24076 KB	Output is correct
10	Correct	2445 ms	23744 KB	Output is correct