Codeforces Round #344(Div.2) 문제 해결 보고서

631A- Interview
Blake is a CEO of a large company called “Blake Technologies”. He loves his company very much and he thinks that his company should be the best. That is why every candidate needs to pass through the interview that consists of the following problem.
We define function f(x, l, r) as a bitwise OR of integers xl, xl + 1, …, xr, where xi is the i-th element of the array x. You are given two arrays a and b of length n. You need to determine the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.
Input The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the arrays.
The second line contains n integers ai (0 ≤ ai ≤ 109).
The third line contains n integers bi (0 ≤ bi ≤ 109).
Output Print a single integer — the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.
input 5 1 2 4 3 2 2 3 3 12 1 output 22
input 10 13 2 7 11 8 4 9 8 5 1 5 7 18 9 2 3 0 11 8 6 output 46
제목 링크: cf-631A
제목 대의: a, b 두 개의 서열을 제시하고 각각 a, b 임의의 연속값이나 최대값sum1,sum2.를 구한다.출력sum1+sum2
제목 사고방식: 또는 모든 값이면 된다. 왜냐하면 a|b=c, c는 반드시 a보다 크고 b보다 크기 때문이다.
다음은 코드입니다.

#include <bits/stdc++.h>
#define mst(a) memset(a,0,sizeof (a))
#define FOR(i,n) for (int i = 0; i < n; i++)
#define INF 1e9
#define eps 1e-10
using namespace std;

typedef long long ll;
ll a[1005],b[1005];
int main(){
    int n;
    cin >> n;
    ll sum1 = 0,sum2 = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum1 = sum1 | a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        sum2 = sum2 | b[i];
    }
    cout << sum1 + sum2 << endl;
    return 0;
}

631B-Print Check
Kris works in a large company “Blake Technologies”. As a best engineer of the company he was assigned a task to develop a printer that will be able to print horizontal and vertical strips. First prototype is already built and Kris wants to tests it. He wants you to implement the program that checks the result of the printing.
Printer works with a rectangular sheet of paper of size n × m. Consider the list as a table consisting of n rows and m columns. Rows are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m. Initially, all cells are painted in color 0.
Your program has to support two operations:
Paint all cells in row ri in color ai; Paint all cells in column ci in color ai. If during some operation i there is a cell that have already been painted, the color of this cell also changes to ai.
Your program has to print the resulting table after k operation.
Input The first line of the input contains three integers n, m and k (1  ≤  n,  m  ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) — the dimensions of the sheet and the number of operations, respectively.
Each of the next k lines contains the description of exactly one query:
1 ri ai (1 ≤ ri ≤ n, 1 ≤ ai ≤ 109), means that row ri is painted in color ai; 2 ci ai (1 ≤ ci ≤ m, 1 ≤ ai ≤ 109), means that column ci is painted in color ai. Output Print n lines containing m integers each — the resulting table after all operations are applied.
input 3 3 3 1 1 3 2 2 1 1 2 2 output 3 1 3 2 2 2 0 1 0
input 5 3 5 1 1 1 1 3 1 1 5 1 2 1 1 2 3 1 output 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
제목 링크: cf-631B
제목 대의: n*m의 칸을 주고 처음에 색을 0으로 채우면 k회 조작이 있고 매번 a, b,val을 입력하면 두 가지 선택이 있습니다.

a == 1; b행을 모두 색상으로 변경합니다 val

a == 2; b열을 모두 색상으로 변경합니다 val

제목 사고방식: 원래의 생각은 2차원 라인 트리를 사용하지만 쓸 수 없다.그리고 직접 폭력, 처음 테스트, 그러나 최종 테스트, 예상 orz
비헤이비어를 예로 들면 다음과 같습니다.
매번 수정할 때마다 r[b] = val;//수정 b행의 색상은 val입니다.
또한 이번 수정을 기록한 조작은 몇 번째입니다.//뒤에 수정된 색상은 원래 색상을 덮어씁니다.
같은 이치에 속하다.
마지막으로 처리할 때 i행 j열의 요소는 i행의 마지막 수정이 몇 번째인지, j열의 마지막 수정이 몇 번째인지를 비교한다.비교적 큰 것이 답이다.
다음은 코드입니다.

#include <bits/stdc++.h>
#define mst(a) memset(a,0,sizeof (a))
#define FOR(i,n) for (int i = 0; i < n; i++)
#define INF 1e9
#define eps 1e-10
using namespace std;

typedef long long ll;
int r[5005],c[5005],ret1[5005],ret2[5005];
int main(){
    int n,m,k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)  // 1   
    {
        int a,b,val;
        cin >> a >> b >> val;
        if (a == 1)
        {
            r[b] = val;
            ret1[b] = i;  //           i   
        }
        else
        {
            c[b] = val;
            ret2[b] = i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (ret1[i] > ret2[j]) cout << r[i] << " ";  //   i    
            else cout << c[j] << " ";  //   j    
        }
        cout << endl;
    }
    return 0;
}

631C-Report
Each month Blake gets the report containing main economic indicators of the company “Blake Technologies”. There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first ri numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).
Employees of the “Blake Technologies” are preparing the report right now. You know the initial sequence ai of length n and the description of each manager, that is value ri and his favourite order. You are asked to speed up the process and determine how the final report will look like.
Input The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.
The second line contains n integers ai (|ai| ≤ 109) — the initial report before it gets to the first manager.
Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers ti and ri (, 1 ≤ ri ≤ n), meaning that the i-th manager sorts the first ri numbers either in the non-descending (if ti = 1) or non-ascending (if ti = 2) order.
Output Print n integers — the final report, which will be passed to Blake by manager number m.
input 3 1 1 2 3 2 2 output 2 1 3
input 4 2 1 2 4 3 2 3 1 2 output 2 4 1 3
제목 링크: cf-631C
제목의 대의: 하나의 서열을 주고 m회 조작하며 매번 다음과 같다. [1,ri]를 승차순/강차순으로 배열한다.최종 서열을 구하다.
제목 사고방식: 이 문제는 내가 아직 해결하지 못했다
참조 블로그:here