oj.uz

Submission #454739

# Submission time Handle Problem Language Result Execution time Memory
454739 2021-08-05T07:44:13 Z Josia Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 537 ms 27572 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])%mod;
}


void updatePos(int v, int rl, int rr, int pos, int val) {
    push(v);
    if (rl == rr) {
        tree[v] += val;
        tree[v] %= mod;
//        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])%mod;
}

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))%mod;
}







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])%mod;
}


void updatePos2(int v, int rl, int rr, int pos, int val) {
    push2(v);
    if (rl == rr) {
        tree2[v] += (val * calcOptions(dictReverse[pos]))%mod;
        tree2[v] %= mod;
        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])%mod;
}


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))%mod;
}




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:91: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]
   91 |     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:148: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]
  148 |     for (int i = 0; i<height.size(); i++) {
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16204 KB Output is correct
2 Correct 12 ms 16332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16184 KB Output is correct
2 Correct 9 ms 16204 KB Output is correct
3 Correct 8 ms 16204 KB Output is correct
4 Correct 8 ms 16204 KB Output is correct
5 Correct 8 ms 16204 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16204 KB Output is correct
2 Correct 11 ms 16192 KB Output is correct
3 Correct 152 ms 18648 KB Output is correct
4 Correct 310 ms 21188 KB Output is correct
5 Correct 317 ms 21176 KB Output is correct
6 Correct 324 ms 21164 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16332 KB Output is correct
2 Correct 37 ms 16852 KB Output is correct
3 Correct 156 ms 19084 KB Output is correct
4 Correct 320 ms 21948 KB Output is correct
5 Correct 333 ms 22084 KB Output is correct
6 Correct 8 ms 16196 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16204 KB Output is correct
2 Correct 11 ms 16296 KB Output is correct
3 Correct 37 ms 16844 KB Output is correct
4 Correct 157 ms 19100 KB Output is correct
5 Correct 334 ms 21952 KB Output is correct
6 Correct 315 ms 22064 KB Output is correct
7 Correct 12 ms 16236 KB Output is correct
8 Correct 43 ms 17248 KB Output is correct
9 Correct 169 ms 20304 KB Output is correct
10 Correct 345 ms 27448 KB Output is correct
11 Correct 352 ms 27540 KB Output is correct
12 Correct 8 ms 16204 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16204 KB Output is correct
2 Correct 13 ms 16332 KB Output is correct
3 Correct 9 ms 16188 KB Output is correct
4 Correct 8 ms 16204 KB Output is correct
5 Correct 8 ms 16136 KB Output is correct
6 Correct 8 ms 16204 KB Output is correct
7 Correct 8 ms 16172 KB Output is correct
8 Correct 13 ms 16204 KB Output is correct
9 Correct 11 ms 16176 KB Output is correct
10 Correct 11 ms 16296 KB Output is correct
11 Correct 8 ms 16152 KB Output is correct
12 Correct 11 ms 16192 KB Output is correct
13 Correct 12 ms 16276 KB Output is correct
14 Correct 12 ms 16276 KB Output is correct
15 Correct 12 ms 16204 KB Output is correct
16 Correct 9 ms 16204 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16204 KB Output is correct
2 Correct 12 ms 16332 KB Output is correct
3 Correct 8 ms 16204 KB Output is correct
4 Correct 12 ms 16348 KB Output is correct
5 Correct 8 ms 16204 KB Output is correct
6 Correct 8 ms 16204 KB Output is correct
7 Correct 8 ms 16124 KB Output is correct
8 Correct 8 ms 16184 KB Output is correct
9 Correct 9 ms 16204 KB Output is correct
10 Correct 13 ms 16280 KB Output is correct
11 Correct 152 ms 18740 KB Output is correct
12 Correct 307 ms 21308 KB Output is correct
13 Correct 312 ms 21264 KB Output is correct
14 Correct 300 ms 21180 KB Output is correct
15 Correct 11 ms 16196 KB Output is correct
16 Correct 38 ms 16844 KB Output is correct
17 Correct 155 ms 19136 KB Output is correct
18 Correct 335 ms 22028 KB Output is correct
19 Correct 313 ms 22076 KB Output is correct
20 Correct 11 ms 16332 KB Output is correct
21 Correct 43 ms 17272 KB Output is correct
22 Correct 171 ms 20300 KB Output is correct
23 Correct 373 ms 27444 KB Output is correct
24 Correct 355 ms 27552 KB Output is correct
25 Correct 10 ms 16204 KB Output is correct
26 Correct 13 ms 16256 KB Output is correct
27 Correct 12 ms 16328 KB Output is correct
28 Correct 11 ms 16204 KB Output is correct
29 Correct 11 ms 16296 KB Output is correct
30 Correct 50 ms 17324 KB Output is correct
31 Correct 51 ms 17356 KB Output is correct
32 Correct 194 ms 19032 KB Output is correct
33 Correct 252 ms 21888 KB Output is correct
34 Correct 520 ms 27060 KB Output is correct
35 Correct 385 ms 21864 KB Output is correct
36 Correct 537 ms 27552 KB Output is correct
37 Correct 479 ms 25080 KB Output is correct
38 Correct 10 ms 16204 KB Output is correct
39 Correct 466 ms 24344 KB Output is correct
40 Correct 520 ms 27448 KB Output is correct
41 Correct 398 ms 27444 KB Output is correct
42 Correct 388 ms 27572 KB Output is correct