oj.uz

답안 #156370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156370 2019-10-05T11:32:49 Z Moses Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 33616 KB 
// Created by AboAbdoMC
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lll long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int OO = 1e4+7;
const int MOD = 1e9+7;
const int N = 1e5+7;
const int C = 27;
int n,c,q;
int a[N],b[N],st[N*4][C];

struct node {
  int ll, rr, id;

  node(int L, int R, int X) { 
    ll=L, rr=R, id=X; 
  }

  node left() 
    { return node(ll, (ll+rr)/2, id*2); }
  node right() 
    { return node((ll+rr)/2+1, rr, id*2+1); }
  
  void update(int pos){ // don't need to call lazy_update() at the beginning
  	repA(i,0,c) st[id][i] = 0;
    if (ll == rr) 
	{
		st[id][0] = b[pos]%MOD;
		st[id][1] = a[pos]%MOD;
		return;
	} 
    if (pos <= (ll+rr)/2) left().update(pos); // easier to read
    else right().update(pos);
    
    repA(i,0,c)
    {
    	repA(j,0,c)
    	{
    		int k = min(i+j,c);
    		st[id][k] += (st[right().id][i]*st[left().id][j])%MOD;
    		st[id][k] %= MOD;
    	}
    }
  }

};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> c;
    repA(i,1,n)
    {
    	cin >> a[i] >> b[i];
    	node(1,n,1).update(i);
    }



    cin >> q;
    while(q--)
    {
    	int p;
    	cin >> p;
    	cin >> a[p] >> b[p];
    	node(1,n,1).update(p);
    	cout << st[1][c] << '\n';
    }
    return 0;
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 632 KB Output isn't correct
2 Incorrect 26 ms 632 KB Output isn't correct
3 Incorrect 52 ms 576 KB Output isn't correct
4 Incorrect 945 ms 18092 KB Output isn't correct
5 Runtime error 3921 ms 33368 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Execution timed out 4034 ms 30896 KB Time limit exceeded
7 Incorrect 2472 ms 18348 KB Output isn't correct
8 Incorrect 1488 ms 32572 KB Output isn't correct
9 Runtime error 2116 ms 33616 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Execution timed out 4006 ms 30440 KB Time limit exceeded