Submission #453786

#	Time	Username	Problem	Language	Result	Execution time	Memory
453786		Josia	Fancy Fence (CEOI20_fancyfence)	C++17	12 / 100	12 ms	16296 KiB

fancyfence

#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;

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 * ((dictReverse[pos]+1.0)/2.0 * 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;
//        cout << resOverlap << "\n";
        resOneSeg += int((w+1.0)/2.0 * w)%mod * int((dictReverse[h]+1.0)/2.0 * dictReverse[h])%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 (stderr)

fancyfence.cpp: In function 'void push(int64_t)':
fancyfence.cpp:16: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]
   16 |     if (v*2+1 >= tree.size()) return;
      |         ~~~~~~^~~~~~~~~~~~~~
fancyfence.cpp: In function 'void push2(int64_t)':
fancyfence.cpp:78: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]
   78 |     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:134: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]
  134 |     for (int i = 0; i<height.size(); i++) {
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27