oj.uz

Submission #289714

# Submission time Handle Problem Language Result Execution time Memory
289714 2020-09-02T23:28:35 Z b00n0rp Horses (IOI15_horses) C++17
100 / 100
 585 ms 49276 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

int power(int a,int b,int m = MOD){
    if(b == 0) return 1;
    if(b == 1) return a;
    int x = power(a,b/2,m)%m;
    x = (x*x)%m;
    if(b%2) return (x*a)%m;
    return x;
}

int n,x[500005],y[500005],q,seg[1000005],seg2[1000005];
int seg3[1000005];

int quer(int l,int r){
    // cout << l << " " << r << " ----> ";
    l += n;
    r += n+1;
    int ans = 1;
    while(l < r){
        if(l%2){
            ans *= seg2[l++];
            remin(ans,(ll)2e9);
        }
        if(r%2){
            ans *= seg2[--r];
            remin(ans,(ll)2e9);
        }
        l /= 2;
        r /= 2;
    }
    // cout << ans << endl;
    return ans;
}

int quer2(int pos){
    int ans = y[pos];
    int l = n,r = pos+n+1;
    while(l < r){
        if(l%2) ans = (ans*seg3[l++])%MOD;
        if(r%2) ans = (ans*seg3[--r])%MOD;
        l /= 2;
        r /= 2;
    }
    return ans;
}

signed init(signed _n, signed _X[], signed _Y[]) {
    n = _n;
    REP(i,n) x[i] = _X[i],seg2[i+n] = x[i],seg3[i+n] = x[i];
    REP(i,n) y[i] = _Y[i],seg[i+n] = i;
    for(int i = n-1; i > 0; i --){
        seg2[i] = min((ll)2e9,seg2[i*2]*seg2[i*2+1]);
        seg3[i] = (seg3[i*2]*seg3[i*2+1])%MOD;
    }
    for(int i = n-1; i > 0; i --){
        int left = seg[i*2],right = seg[i*2+1];
        if(left > right) swap(left,right);
        if(quer(left+1,right)*y[right] > y[left]){
            seg[i] = right;
        }
        else seg[i] = left;
    }
    return (signed)quer2(seg[1]);
}
 
signed updateX(signed pos, signed val) { 
    x[pos] = val;
    seg2[pos+n] = val;
    seg3[pos+n] = val;
    
    pos += n;
    for(int i = pos/2; i > 0; i /= 2){
        seg2[i] = min((ll)2e9,seg2[i*2]*seg2[i*2+1]);
        seg3[i] = (seg3[i*2]*seg3[i*2+1])%MOD;
    }
    if(n <= 1000 and q <= 1000){
        for(int i = pos/2; i > 0; i --){
            int left = seg[i*2],right = seg[i*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[i] = right;
            }
            else seg[i] = left;
        }
    }
    else{
        for(int i = pos/2; i > 0; i /= 2){
            //-----------------------------------------
            int j = i+1;
            int left = seg[j*2],right = seg[j*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[j] = right;
            }
            else seg[j] = left;
            //-----------------------------------------
            left = seg[i*2],right = seg[i*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[i] = right;
            }
            else seg[i] = left;
            //-----------------------------------------
            j = i-1;
            left = seg[j*2],right = seg[j*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[j] = right;
            }
            else seg[j] = left;
            //-----------------------------------------
        }
    }
    return (signed)quer2(seg[1]);
}
 
signed updateY(signed pos, signed val) {
    y[pos] = val;
    
    pos += n;
    for(int i = pos/2; i > 0; i /= 2){
        seg2[i] = min((ll)2e9,seg2[i*2]*seg2[i*2+1]);
        seg3[i] = (seg3[i*2]*seg3[i*2+1])%MOD;
    }
    if(n <= 1000 and q <= 1000){
        for(int i = pos/2; i > 0; i --){
            int left = seg[i*2],right = seg[i*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[i] = right;
            }
            else seg[i] = left;
        }
    }
    else{
        for(int i = pos/2; i > 0; i /= 2){
            //-----------------------------------------
            int j = i+1;
            int left = seg[j*2],right = seg[j*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[j] = right;
            }
            else seg[j] = left;
            //-----------------------------------------
            left = seg[i*2],right = seg[i*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[i] = right;
            }
            else seg[i] = left;
            //-----------------------------------------
            j = i-1;
            left = seg[j*2],right = seg[j*2+1];
            if(left > right) swap(left,right);
            if(quer(left+1,right)*y[right] > y[left]){
                seg[j] = right;
            }
            else seg[j] = left;
            //-----------------------------------------
        }
    }
    return (signed)quer2(seg[1]);
}

Compilation message

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:103:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |     pos += n;
      |     ~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:152:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |     pos += n;
      |     ~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 40436 KB Output is correct
2 Correct 414 ms 47736 KB Output is correct
3 Correct 453 ms 40312 KB Output is correct
4 Correct 451 ms 44484 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 9 ms 544 KB Output is correct
24 Correct 9 ms 512 KB Output is correct
25 Correct 8 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 8 ms 512 KB Output is correct
28 Correct 8 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 7 ms 512 KB Output is correct
31 Correct 5 ms 512 KB Output is correct
32 Correct 7 ms 512 KB Output is correct
33 Correct 101 ms 39596 KB Output is correct
34 Correct 101 ms 39544 KB Output is correct
35 Correct 95 ms 46612 KB Output is correct
36 Correct 93 ms 46456 KB Output is correct
37 Correct 88 ms 37880 KB Output is correct
38 Correct 66 ms 38744 KB Output is correct
39 Correct 64 ms 37624 KB Output is correct
40 Correct 100 ms 41556 KB Output is correct
41 Correct 61 ms 37788 KB Output is correct
42 Correct 60 ms 37752 KB Output is correct
43 Correct 53 ms 41976 KB Output is correct
44 Correct 53 ms 41976 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 9 ms 512 KB Output is correct
24 Correct 9 ms 512 KB Output is correct
25 Correct 8 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 8 ms 512 KB Output is correct
28 Correct 8 ms 512 KB Output is correct
29 Correct 8 ms 384 KB Output is correct
30 Correct 8 ms 512 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 7 ms 512 KB Output is correct
33 Correct 255 ms 40568 KB Output is correct
34 Correct 432 ms 49276 KB Output is correct
35 Correct 456 ms 40476 KB Output is correct
36 Correct 463 ms 44572 KB Output is correct
37 Correct 96 ms 39544 KB Output is correct
38 Correct 99 ms 39544 KB Output is correct
39 Correct 96 ms 46456 KB Output is correct
40 Correct 110 ms 46492 KB Output is correct
41 Correct 87 ms 37752 KB Output is correct
42 Correct 63 ms 38648 KB Output is correct
43 Correct 64 ms 37624 KB Output is correct
44 Correct 76 ms 41592 KB Output is correct
45 Correct 60 ms 37752 KB Output is correct
46 Correct 62 ms 37752 KB Output is correct
47 Correct 53 ms 41976 KB Output is correct
48 Correct 54 ms 41976 KB Output is correct
49 Correct 585 ms 41740 KB Output is correct
50 Correct 558 ms 41720 KB Output is correct
51 Correct 298 ms 48504 KB Output is correct
52 Correct 299 ms 47992 KB Output is correct
53 Correct 522 ms 40184 KB Output is correct
54 Correct 278 ms 40568 KB Output is correct
55 Correct 319 ms 38776 KB Output is correct
56 Correct 301 ms 43384 KB Output is correct
57 Correct 263 ms 39292 KB Output is correct
58 Correct 297 ms 39948 KB Output is correct
59 Correct 53 ms 41976 KB Output is correct