oj.uz

답안 #453788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
453788 2021-08-04T20:18:15 Z Josia Fancy Fence (CEOI20_fancyfence) C++17
25 / 100
 278 ms 21260 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define int int64_t

vector<int> tree;
vector<bool> lazy;
map<int, int> dict;
vector<int> dictReverse;
int mod = 1000000007;


int calcOptions(int x) {
    if (x%2) {
//        cout << ((x+1)/2 * x)%mod << "blub\n";
        return ((x+1)/2 * x)%mod;
    } else {
        return (x/2 * x + x/2)%mod;
    }
}



void push(int v) {
    if (v*2+1 >= tree.size()) return;
    lazy[v*2] = lazy[v*2]||lazy[v];
    lazy[v*2+1] = 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*2]||lazy2[v];
    lazy2[v*2+1] = 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 * calcOptions(dictReverse[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);
}




pair<vector<int>, vector<int>> simplify(vector<int> height, vector<int> width) {
    vector<int> newheight; vector<int> newwidth;
    
    for (int i = 0; i<height.size(); i++) {
        for (int j = 0; j<width[i]; j++) {
            newheight.push_back(height[i]);
            newwidth.push_back(1);
        }
    }
    return {newheight, newwidth};
}



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;
    
//    pair<vector<int>, vector<int>> blub = simplify(height, width);
//
//    height = blub.first;
//    width = blub.second;

    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);
    }
    
    vector<int> sortedHeight = height;
    sort(sortedHeight.begin(), sortedHeight.end());
    int counter = 0;
    for (int i: sortedHeight) {
        dict[i]=counter;
        dictReverse.push_back(i);
        counter++;
    }

    int valBefore = 0;
    int resOverlap = 0;
    int resOneSeg = 0;

    for (int i = 0; i<n; i++) {
        int h = dict[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)%mod;
//        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)%mod;
        resOverlap %= mod;
//        cout << resOneSeg << "\n";
        resOneSeg += (calcOptions(w) * calcOptions(dictReverse[h]))%mod;
        resOneSeg %= mod;
    }

    cout << (resOverlap + resOneSeg)%mod << "\n";
//    cout << resOverlap << " + " << resOneSeg << "\n";


    return 0;
}


//signed main() {
//    int n, q; cin >> n >> q;
//    tree.assign(n*4, 0);
//    lazy.assign(n*4, 0);
//    tree2.assign(n*4, 0);
//    lazy2.assign(n*4, 0);
//
//    for (int i = 0; i<q; i++) {
//        char c; cin >> c;
//        if (c == 'q') {
//            int left, right; cin >> left >> right;
//            cout << querry(1, 0, n-1, left, right) << "\n";
//        }
//        if (c == 'r') {
//            int left, right; cin >> left >> right;
//            updateRange(1, 0, n-1, left, right);
//        }
//        if (c == 'p') {
//            int pos, val; cin >> pos >> val;
//            updatePos(1, 0, n-1, pos, val);
//        }
//    }
//}

Compilation message

fancyfence.cpp: In function 'void push(int64_t)':
fancyfence.cpp:28: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]
   28 |     if (v*2+1 >= tree.size()) return;
      |         ~~~~~~^~~~~~~~~~~~~~
fancyfence.cpp: In function 'void push2(int64_t)':
fancyfence.cpp:90: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]
   90 |     if (v*2+1 >= tree2.size()) return;
      |         ~~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp: In function 'std::pair<std::vector<long int>, std::vector<long int> > simplify(std::vector<long int>, std::vector<long int>)':
fancyfence.cpp:146:22: 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]
  146 |     for (int i = 0; i<height.size(); i++) {
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16220 KB Output is correct
2 Incorrect 11 ms 16240 KB Output isn't correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16204 KB Output is correct
2 Correct 8 ms 16140 KB Output is correct
3 Correct 8 ms 16208 KB Output is correct
4 Correct 7 ms 16204 KB Output is correct
5 Correct 8 ms 16196 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16204 KB Output is correct
2 Correct 11 ms 16272 KB Output is correct
3 Correct 131 ms 18700 KB Output is correct
4 Correct 268 ms 21228 KB Output is correct
5 Correct 278 ms 21228 KB Output is correct
6 Correct 250 ms 21260 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16220 KB Output is correct
2 Incorrect 11 ms 16240 KB Output isn't correct