oj.uz

답안 #246262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246262 2020-07-08T13:08:01 Z bibabas Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 45476 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-8;
const ll mod = (ll)10007;
const ll MAXN = (ll)1e4 + 1;
const ll MAXC = (ll)1e6 + 1;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll block = 480;
const ld PI = acos(-1);
const ld e = 2.7182818284;
 
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
 
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};

ll c;
ll t[400000][21];

void merge(ll v) {
    for (ll i = 0; i <= 20; ++i) t[v][i] = 0;
    for (ll i = 0; i <= 20; ++i) {
        for (ll j = 0; j <= 20; ++j) {
            t[v][min(c, i + j)] += (t[2 * v][i] * t[2 * v + 1][j]) % mod;
            t[v][min(c, i + j)] %= mod;
        }
    }
}

void build(ll v, ll tl, ll tr, vector<pii> &a) {
    if (tl + 1 == tr) {
        t[v][1] = a[tl].first, t[v][0] = a[tl].second;
        return;
    }
    ll tm = (tl + tr) / 2;
    build(2 * v, tl, tm, a);
    build(2 * v + 1, tm, tr, a);
    merge(v);
}

void upd(ll v, ll tl, ll tr, ll pos, pii val) {
    if (tl + 1 == tr) {
        t[v][1] = val.first, t[v][0] = val.second;
        return;
    }
    ll tm = (tl + tr) / 2;
    if (pos < tm) upd(2 * v, tl, tm, pos, val);
    else upd(2 * v + 1, tm, tr, pos, val);
    merge(v);
}

void solve() {
    ll n; cin >> n >> c;
    vector<pii> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    build(1, 0, n, a);
    ll q; cin >> q;
    while (q--) {
        ll pos; pii a; cin >> pos >> a.first >> a.second;
        pos--;
        upd(1, 0, n, pos, a);
        cout << t[1][c] << "\n";
    }
}

int main() {
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif
    cout.precision(30);
    
    solve();
 
    return 0;
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 640 KB Output isn't correct
2 Incorrect 51 ms 780 KB Output isn't correct
3 Incorrect 35 ms 640 KB Output isn't correct
4 Incorrect 3470 ms 23116 KB Output isn't correct
5 Execution timed out 4081 ms 45348 KB Time limit exceeded
6 Runtime error 3040 ms 45476 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Incorrect 3089 ms 23480 KB Output isn't correct
8 Runtime error 3239 ms 44936 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Execution timed out 4085 ms 45016 KB Time limit exceeded
10 Runtime error 3756 ms 41248 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)