oj.uz

Submission #420217

# Submission time Handle Problem Language Result Execution time Memory
420217 2021-06-08T07:49:01 Z Aldas25 Horses (IOI15_horses) C++14
100 / 100
 1451 ms 64680 KB 
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 500100;
const ll MOD = 1e9+7;

int n;
ll x[MAXN], y[MAXN];

ll tree3[4*MAXN];

void updPref (int p, ll val, int id = 1, int le = 1, int ri = n) {
    if (le == ri){
        tree3[id] = val;
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        updPref(p, val, 2*id, le, mid);
    else
        updPref(p, val, 2*id+1, mid+1, ri);
    tree3[id] = (tree3[2*id] * tree3[2*id+1])%MOD;
}

ll prefX (int fr, int to, int id = 1, int le = 1, int ri = n) {
    if (fr > ri || to < le) return 1;
    if (fr <= le && ri <= to) return tree3[id];
    int mid = (le+ri)/2;
    return (prefX(fr, to, 2*id, le, mid) * prefX(fr, to, 2*id+1, mid+1, ri))%MOD;
}

ll prefX (int p) {
    return prefX(1, p);
}

ll tree2[4*MAXN];

void upd2 (int p, ll val, int id = 1, int le = 1, int ri = n) {
    if (le == ri){
        tree2[id] = val;
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        upd2(p, val, 2*id, le, mid);
    else
        upd2(p, val, 2*id+1, mid+1, ri);
    tree2[id] = tree2[2*id] + tree2[2*id+1];
}

ll get2 (int fr, int to, int id = 1, int le = 1, int ri = n) {
    if (fr > ri || to < le) return 0;
    if (fr <= le && ri <= to) return tree2[id];
    int mid = (le+ri)/2;
    return get2(fr, to, 2*id, le, mid) + get2(fr, to, 2*id+1, mid+1, ri);
}

ll get2 (int p) {
    return get2(1, p);
}

int getId (ll sum, int id = 1, int le = 1, int ri = n) {
    if (le == ri) return le;
    int mid = (le+ri)/2;
    if (sum <= tree2[2*id]) return getId(sum, 2*id, le, mid);
    else return getId(sum-tree2[2*id], 2*id+1, mid+1, ri);
}

ll tree[4*MAXN];
void updTree (int p, ll val, int id =  1, int le = 1, int ri = n) {
    if (le == ri){
        tree[id] = le;
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        updTree(p, val, 2*id, le, mid);
    else
        updTree(p, val, 2*id+1, mid+1, ri);
    if (y[tree[2*id]] > y[tree[2*id+1]])
        tree[id] = tree[2*id];
    else
        tree[id] = tree[2*id+1];
}

ll getMaxY (int fr, int to, int id = 1, int le = 1, int ri = n) {
    if (fr > ri || to < le) return 0;
    if (fr <= le && ri <= to) return tree[id];
    int mid = (le+ri)/2;
    ll id1 = getMaxY(fr, to, 2*id, le, mid);
    ll id2 = getMaxY(fr, to, 2*id+1, mid+1, ri);
    if (y[id1] > y[id2]) return id1;
    else return id2;
}

void print (){
    FOR(i, 1, n) {
        cout << " i = " << i << endl;
        cout << "    x = " << x[i] << " y = " << y[i] << endl;
        cout << "    prefX = " << prefX(i) << endl;
        cout << "    get2 pref = " << get2(i) << " get2 i = " << get2(i,i) << endl;
        cout << "    maxY i = " << getMaxY(i, i) << "  getMaxY pref = " << getMaxY(1, i) << endl;
    }
}

set<int> spec;

ll getMax () {
    int id = 1;
   // ll tot = get2(1,n);
    auto it = spec.end();
    REP(32) {
        if (it == spec.begin()) break;
        it--;
    }
    if (it != spec.begin()) {
        it--;
        id = *it;
        it++;
    }

    ll cr = 1;
    FOR(i, id+1, n) {

        //cout << " i = " << i << " id = " << id << endl;

        if (x[i] > 1) {
            cr *= x[i];
            if (cr * y[i] > y[id]) {
                id = i;
                cr = 1;
            }
            //cout << "   case xi > 1, id = " << id << endl;
        } else {
            int le = n;
            while (it != spec.end() && (*(it)) <= i) {
                //cout << "             le = " << le << "  *it = " << (*(it)) << endl;
                it++;
            }
            if (it != spec.end())
                le = (*(it)) - 1;
            /// [i;le] all x are equal to 1
            int mxId = getMaxY(i, le);
           // cout << "   case xi = 1,  le = " << le << endl;
            if (cr * y[mxId] > y[id]) {
                id = mxId;
                cr = 1;
            }
            i = le;
           // cout << "       id = " << id << " i = " << i << endl;
        }
    }

    //cout << " final id = " << id << endl;

    ll ret = (prefX(id) * y[id])%MOD;

    //cout << "  prefX = " << prefX(id) << " y = " << y[id] << endl;
    //print();

    return ret;
}

int init(int N, int X[], int Y[]) {
    n = N;
    FOR(i, 1, n) x[i] = X[i-1];
    FOR(i, 1, n) y[i] = Y[i-1];
//    FOR(i, 0, MAXN-1) fen[i] = 1;
    FOR(i, 1, n) updPref (i, x[i]);
   // FOR(i, 1, n) upd2(i, (x[i] > 1));
    FOR(i, 1, n) updTree(i, y[i]);
    FOR(i, 1, n) if (x[i] > 1) spec.insert(i);

	return getMax();
}

int updateX(int pos, int val) {
    pos++;
    //updPref (pos, modInv(x[pos]));
    //if (x[pos] > 1) upd2(pos, -1);
    if (x[pos] > 1) spec.erase(pos);
    x[pos] = val;
    updPref (pos, x[pos]);
    //if (x[pos] > 1) upd2(pos, 1);
    if (x[pos] > 1) spec.insert(pos);
   // upd2(pos, (x[pos] > 1));
	return getMax();
}

int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
    updTree(pos, y[pos]);
	return getMax();
}


/*

3
2 1 3
3 4 1
1
2 1 2
ans: 8 6

10
2 1 1 1 1 2 1 1 1 1
4 5 6 1 4 5 6 1 100 1
0
ans: 400

*/

Compilation message

horses.cpp: In function 'll getMax()':
horses.cpp:157:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  157 |             int mxId = getMaxY(i, le);
      |                        ~~~~~~~^~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:188:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  188 |  return getMax();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:201:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  201 |  return getMax();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:208:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  208 |  return getMax();
      |         ~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 216 KB Output is correct
13 Correct 1 ms 216 KB Output is correct
14 Correct 0 ms 216 KB Output is correct
15 Correct 1 ms 216 KB Output is correct
16 Correct 1 ms 216 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 216 KB Output is correct
21 Correct 1 ms 216 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 6 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 5 ms 392 KB Output is correct
28 Correct 5 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 3 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 6 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 52996 KB Output is correct
2 Correct 559 ms 52936 KB Output is correct
3 Correct 541 ms 52932 KB Output is correct
4 Correct 628 ms 52896 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 216 KB Output is correct
19 Correct 1 ms 216 KB Output is correct
20 Correct 1 ms 216 KB Output is correct
21 Correct 1 ms 216 KB Output is correct
22 Correct 0 ms 216 KB Output is correct
23 Correct 6 ms 344 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 5 ms 344 KB Output is correct
28 Correct 5 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 5 ms 332 KB Output is correct
33 Correct 362 ms 28660 KB Output is correct
34 Correct 245 ms 28664 KB Output is correct
35 Correct 426 ms 52044 KB Output is correct
36 Correct 411 ms 52036 KB Output is correct
37 Correct 342 ms 28612 KB Output is correct
38 Correct 350 ms 40500 KB Output is correct
39 Correct 240 ms 28476 KB Output is correct
40 Correct 378 ms 52076 KB Output is correct
41 Correct 228 ms 28520 KB Output is correct
42 Correct 298 ms 28560 KB Output is correct
43 Correct 366 ms 51968 KB Output is correct
44 Correct 373 ms 51848 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 6 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 5 ms 332 KB Output is correct
28 Correct 4 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 436 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 6 ms 332 KB Output is correct
33 Correct 502 ms 52848 KB Output is correct
34 Correct 532 ms 52868 KB Output is correct
35 Correct 511 ms 52932 KB Output is correct
36 Correct 598 ms 53056 KB Output is correct
37 Correct 360 ms 28612 KB Output is correct
38 Correct 253 ms 28804 KB Output is correct
39 Correct 407 ms 52036 KB Output is correct
40 Correct 422 ms 52008 KB Output is correct
41 Correct 349 ms 28604 KB Output is correct
42 Correct 362 ms 40460 KB Output is correct
43 Correct 239 ms 28496 KB Output is correct
44 Correct 404 ms 52012 KB Output is correct
45 Correct 224 ms 28536 KB Output is correct
46 Correct 305 ms 28480 KB Output is correct
47 Correct 373 ms 51944 KB Output is correct
48 Correct 370 ms 51856 KB Output is correct
49 Correct 1451 ms 31008 KB Output is correct
50 Correct 368 ms 35588 KB Output is correct
51 Correct 639 ms 64680 KB Output is correct
52 Correct 474 ms 64284 KB Output is correct
53 Correct 1362 ms 33848 KB Output is correct
54 Correct 911 ms 47356 KB Output is correct
55 Correct 403 ms 31548 KB Output is correct
56 Correct 534 ms 59812 KB Output is correct
57 Correct 322 ms 32196 KB Output is correct
58 Correct 1084 ms 32744 KB Output is correct
59 Correct 394 ms 58252 KB Output is correct