oj.uz

답안 #453604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
453604 2021-08-04T12:54:26 Z Josia Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 13 ms 16280 KB 
#include <iostream>
#include <vector>
using namespace std;

#define int int64_t

vector<int> tree;
vector<bool> lazy;


void push(int v) {
    if (v*2+1 >= tree.size()) return;
    lazy[v*2] = lazy[v];
    lazy[v*2+1] = lazy[v];

    if (lazy[v]){
        tree[v*2] = 0;
        tree[v*2+1] = 0;
    }
    lazy[v] = 0;
}

void updateRange(int v, int rl, int rr, int ql, int qr) {
    if (ql > qr) return;
    push(v);
    if (rl == ql && rr == qr) {
//        cout << rl << " " << rr << "\n";
        tree[v] = 0;
        lazy[v] = 1;
        return;
    }
    int rm = (rl + rr) / 2;
    
    updateRange(v*2, rl, rm, ql, min(rm, qr));
    updateRange(v*2+1, rm+1, rr, max(ql, rm+1), qr);
    tree[v] = tree[v*2] + tree[v*2+1];
}


void updatePos(int v, int rl, int rr, int pos, int val) {
    push(v);
    if (rl == rr) {
        tree[v] += val;
//        cout << rl << " blub\n";
        return;
    }
    int rm = (rl + rr) / 2;
    
    if (pos <= rm) updatePos(v*2, rl, rm, pos, val);
    else updatePos(v*2+1, rm+1, rr, pos, val);
    tree[v] = tree[v*2] + tree[v*2+1];
}

int querry(int v, int rl, int rr, int ql, int qr) {
    if (ql > qr) return 0;
    push(v);
    if (rl == ql && rr == qr) {
        return tree[v];
    }
    int rm = (rl + rr) / 2;
    return querry(v*2, rl, rm, ql, min(qr, rm)) + querry(v*2+1, rm+1, rr, max(ql, rm+1), qr);
}







vector<int> tree2;
vector<bool> lazy2;


void push2(int v) {
    if (v*2+1 >= tree2.size()) return;
    lazy2[v*2] = lazy2[v];
    lazy2[v*2+1] = lazy2[v];

    if (lazy2[v]){
        tree2[v*2] = 0;
        tree2[v*2+1] = 0;
    }
    lazy2[v] = 0;
}

void updateRange2(int v, int rl, int rr, int ql, int qr) {
    if (ql > qr) return;
    push2(v);
    if (rl == ql && rr == qr) {
        tree2[v] = 0;
        lazy2[v] = 1;
        return;
    }
    int rm = (rl + rr) / 2;
    
    updateRange2(v*2, rl, rm, ql, min(rm, qr));
    updateRange2(v*2+1, rm+1, rr, max(ql, rm+1), qr);
    tree2[v] = tree2[v*2] + tree2[v*2+1];
}


void updatePos2(int v, int rl, int rr, int pos, int val) {
    push2(v);
    if (rl == rr) {
        tree2[v] += val * ((pos+1.0)/2.0 * pos);
        return;
    }
    int rm = (rl + rr) / 2;
    
    if (pos <= rm) updatePos2(v*2, rl, rm, pos, val);
    else updatePos2(v*2+1, rm+1, rr, pos, val);
    tree2[v] = tree2[v*2] + tree2[v*2+1];
}


int querry2(int v, int rl, int rr, int ql, int qr) {
    if (ql > qr) return 0;
    push2(v);
    if (rl == ql && rr == qr) {
        return tree2[v];
    }
    int rm = (rl + rr) / 2;
    return querry2(v*2, rl, rm, ql, min(qr, rm)) + querry2(v*2+1, rm+1, rr, max(ql, rm+1), qr);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    
    tree.assign(1000000, 0);
    lazy.assign(1000000, 0);
    tree2.assign(1000000, 0);
    lazy2.assign(1000000, 0);

    vector<int> height;
    vector<int> width;
    
    for (int i = 0; i<n; i++) {
        int tmp; cin >> tmp; height.push_back(tmp);
    }
    for (int i = 0; i<n; i++) {
        int tmp; cin >> tmp; width.push_back(tmp);
    }
    
    int valBefore = 0;
    int resOverlap = 0;
    int resOneSeg = 0;

    for (int i = 0; i<n; i++) {
        int h = height[i];
        int w = width[i];
        
//        cout << h << " " << w << "\n";
//        for (int i=0; i<10; i++) {
//            cout << querry(1, 0, 100000, i, i) << " ";
//        }
//        cout << "\n";
        
        
        int tooBigSum = querry(1, 0, 100000, h, 100000);
        updateRange(1, 0, 100000, h, 100000);
        updateRange2(1, 0, 100000, h, 100000);
        updatePos(1, 0, 100000, h, tooBigSum);
        updatePos2(1, 0, 100000, h, tooBigSum);
        
        valBefore = querry2(1, 0, 100000, 0, 100000);
//        for (int i=0; i<10; i++) {
//            cout << querry(1, 0, 100000, i, i) << " ";
//        }
//        cout << "\n";
        
        
        updatePos(1, 0, 100000, h, w);
        updatePos2(1, 0, 100000, h, w);
        
//        cout << querry(1, 0, 100000, h, h) << "\n";
        
        resOverlap += valBefore * w;
//        cout << resOverlap << "\n";
        resOneSeg += ((w+1.0)/2.0 * w) * ((h+1.0)/2.0 * h);
    }
    
    cout << resOverlap + resOneSeg << "\n";
//    cout << resOverlap << " + " << resOneSeg << "\n";


    return 0;
}

Compilation message

fancyfence.cpp: In function 'void push(int64_t)':
fancyfence.cpp:12:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (v*2+1 >= tree.size()) return;
      |         ~~~~~~^~~~~~~~~~~~~~
fancyfence.cpp: In function 'void push2(int64_t)':
fancyfence.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     if (v*2+1 >= tree2.size()) return;
      |         ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16204 KB Output is correct
2 Incorrect 10 ms 16192 KB Output isn't correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 16108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16204 KB Output is correct
2 Incorrect 11 ms 16148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16184 KB Output is correct
2 Incorrect 13 ms 16204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16184 KB Output is correct
2 Incorrect 10 ms 16280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16204 KB Output is correct
2 Incorrect 10 ms 16192 KB Output isn't correct