oj.uz

답안 #220232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220232 2020-04-07T11:55:32 Z Haunted_Cpp Relativnost (COCI15_relativnost) C++17
0 / 140
 1859 ms 39920 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
 
/*
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};
 
const int MOD = 1e4 + 7;
const int N = 1e5 + 1;
const int C = 21 + 1;
 
int add (int &a, int b) {
  int res = a + b;
  while (res >= MOD) res -= MOD;
  return res;
}
 
int mult (int a, int b) {
  int res = a * b;
  if (res >= MOD) res %= MOD;
  return res;
}

int sub (int &a, int b) {
  int res = a - b;
  while (res < 0) res += MOD;
  return res;
}
 
int n, c;
int cor [N], incolor[N];

int seg [4 * N][C];

void build (int l, int r, int node, int where) {
  if (l == r) {
    if (where == 0) seg[node][where] = incolor[l];
    else if (where == 1) seg[node][where] = cor[l];
    else if (where == 21) seg[node][where] = add (incolor[l], cor[l]);
    else seg[node][where] = 0;
  } else {
    int mid = l + (r - l) / 2;
    build (l, mid, 2 * node + 1, where);
    build (mid + 1, r, 2 * node + 2, where);
    if (where == 21) {
      seg[node][where] = mult (seg[2 * node + 1][where], seg[2 * node + 2][where]);
      return;
    }
    F0R (i, where + 1) {
      const int L = i;
      const int R = where - i;
      seg[node][where] = add (seg[node][where], mult (seg[2 * node + 1][L], seg[2 * node + 2][R]));
    }  
  }
}

void update (int l, int r, int node, int where, int delta) {
  if (l > delta || r < delta) return;
  if (l == delta && r == delta) {
    if (where == 0) seg[node][where] = incolor[l];
    else if (where == 1) seg[node][where] = cor[l];
    else if (where == 21) seg[node][where] = add (incolor[l], cor[l]);
    else seg[node][where] = 0;
    return;
  }
  int mid = l + (r - l) / 2;
  update (l, mid, 2 * node + 1, where, delta);
  update (mid + 1, r, 2 * node + 2, where, delta);
  if (where == 21) {
    seg[node][where] = mult (seg[2 * node + 1][where], seg[2 * node + 2][where]);
    return;
  }
  seg[node][where] = 0;
  F0R (i, where + 1) {
    const int L = i;
    const int R = where - i;
    seg[node][where] = add (seg[node][where], mult (seg[2 * node + 1][L], seg[2 * node + 2][R]));
  }
}
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> c;
  F0R (i, n) {
    cin >> cor[i];
    cor[i] %= MOD;
  }
  F0R (i, n) {
    cin >> incolor[i];
    incolor[i] %= MOD;
  }
  memset (seg, 0, sizeof(seg));
  F0R (i, C) build (0, n - 1, 0, i); 
  int q;
  cin >> q;
  while (q--) {
    int cliente, nova_cor, nova_incolor;
    cin >> cliente >> nova_cor >> nova_incolor;
    --cliente;
    cor[cliente] = (nova_cor >= MOD ? nova_cor % MOD : nova_cor);
    incolor[cliente] = (nova_incolor >= MOD ? nova_incolor % MOD : nova_incolor); 
    F0R (i, C) update (0, n - 1, 0, i, cliente);
    int res = seg[0][C - 1];
    F0R (i, c) {
      res = sub (res, seg[0][i]);
    }
    cout << res << '\n';
  }
  return 0;
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 34816 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Runtime error 39 ms 34816 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Runtime error 35 ms 34816 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
4 Runtime error 1276 ms 38328 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Runtime error 1634 ms 39732 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 1362 ms 39532 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Runtime error 1215 ms 38404 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
8 Runtime error 1174 ms 38800 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 1859 ms 39800 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 1801 ms 39920 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)