답안 #246258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246258 2020-07-08T12:56:09 Z bibabas Relativnost (COCI15_relativnost) C++14
0 / 140
4000 ms 45712 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;
};

template<class T>
istream& operator >>(istream &in, pair<T, T> &p) {
    in >> p.first;
    in >> p.second;
    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);
    cin >> a;
    build(1, 0, n, a);
    ll q; cin >> q;
    while (q--) {
        ll pos; pii a; cin >> pos >> a;
        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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 768 KB Output isn't correct
2 Incorrect 51 ms 640 KB Output isn't correct
3 Incorrect 35 ms 768 KB Output isn't correct
4 Incorrect 3423 ms 23728 KB Output isn't correct
5 Execution timed out 4038 ms 45648 KB Time limit exceeded
6 Runtime error 3003 ms 45712 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Incorrect 3050 ms 23800 KB Output isn't correct
8 Runtime error 3212 ms 45232 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Execution timed out 4070 ms 45392 KB Time limit exceeded
10 Runtime error 3764 ms 41344 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)