oj.uz

답안 #156396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156396 2019-10-05T12:17:04 Z Moses Relativnost (COCI15_relativnost) C++14
140 / 140
 3042 ms 23292 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 = 1e4+7;
const int N = 1e5+7;
const int C = 21;
int n,c,q;
int a[N],b[N],st[N*3][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;
    		
    	}
    }
    repA(k,0,c) st[id][k] %= MOD;
  }

  void build()
  {
    if (ll == rr)
    {
        st[id][0] = b[ll]%MOD;
        st[id][1] = a[ll]%MOD;
        return;
    }
    left().build();
    right().build();

    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()
{
    
    scanf("%d%d",&n,&c);
    rep(i,n)
    {
    	scanf("%d",&a[i]);
    	
    }
    rep(i,n)
    {
        scanf("%d",&b[i]);
        
    }

    node(0,n-1,1).build();

    scanf("%d",&q);
    while(q--)
    {
    	int p;
    	scanf("%d",&p);p--;
    	scanf("%d%d",&a[p],&b[p]);
    	node(0,n-1,1).update(p);
    	printf("%d\n",st[1][c]);
    }
    return 0;
}

Compilation message

relativnost.cpp: In function 'int main()':
relativnost.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&c);
     ~~~~~^~~~~~~~~~~~~~
relativnost.cpp:94:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&a[i]);
      ~~~~~^~~~~~~~~~~~
relativnost.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&b[i]);
         ~~~~~^~~~~~~~~~~~
relativnost.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
relativnost.cpp:109:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&p);p--;
      ~~~~~^~~~~~~~~
relativnost.cpp:110:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&a[p],&b[p]);
      ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 508 KB Output is correct
2 Correct 13 ms 504 KB Output is correct
3 Correct 23 ms 552 KB Output is correct
4 Correct 434 ms 11896 KB Output is correct
5 Correct 1367 ms 23120 KB Output is correct
6 Correct 1998 ms 23152 KB Output is correct
7 Correct 898 ms 12024 KB Output is correct
8 Correct 508 ms 22784 KB Output is correct
9 Correct 887 ms 23028 KB Output is correct
10 Correct 3042 ms 23292 KB Output is correct