oj.uz

Submission #921612

# Submission time Handle Problem Language Result Execution time Memory
921612 2024-02-04T08:07:09 Z ByeWorld Horses (IOI15_horses) C++14
34 / 100
 65 ms 40220 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 1e9;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;

ll mul(ll x, ll y){
	ll num = (x*y)%MOD;
	return num;
}

int n;
ll x[MAXN], y[MAXN], mx, idx;
set <int> S;

struct seg {
	ll st[4*MAXN]; 
	void bd(int id, int l, int r){
		if(l==r){
            st[id] = x[l];
            return;
        }
		bd(lf, l, md); bd(rg, md+1, r);
        st[id] = mul(st[lf], st[rg]);
	}
	ll que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return 1;
		return mul(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	ll upd(int id, int l, int r, int x, ll p){
		if(l==r && x==l){
			return st[id] = p;
		}
		if(r<x || x<l) return st[id];
		return st[id] = mul(upd(lf, l, md, x, p), 
            upd(rg, md+1, r, x, p));
	}
} A;
struct segtree {
	ll st[4*MAXN]; // pr[i] * y[i]
	void bd(int id, int l, int r){
		if(l==r){
            st[id] = y[l]; return;
        }
		bd(lf, l, md); bd(rg, md+1, r);
        st[id] = max(st[lf], st[rg]);
	}
	ll que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return -INF;
		return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	ll upd(int id, int l, int r, int x, ll p){
		if(l==r && l==x){
			return st[id] = p;
		}
		if(r<x || x<l) return st[id];
		return st[id] = max(upd(lf, l, md, x, p), 
            upd(rg, md+1, r, x, p));
	}
} B;

vector <pii> cand;
int calc(){
    cand.clear();
	auto it = S.end();
    int L = -1, R = n; 
    ll mY = -1;
    for (int i=0;i<30;i++) {
        --it;
        L = *it;
        mY = B.que(1, 1, n, L, R);
        cand.pb(pii(mY, L));
        R = L-1;
        if (R == 0) { // udh keluar
            break;
        }
    }
    
    ll opt = 0, prod=1;
    for (int i=0;i<cand.size();i++) {
        if (cand[opt].fi*prod < cand[i].fi) {
            opt = i;
            prod = 1;
        }
        prod *= x[cand[i].se];
        if (prod > INF) {
            break;
        }
    }
    ll ans = mul(A.que(1, 1, n, 1, cand[opt].se), 
        cand[opt].fi);
    return (int)(ans);
}

int init(int N, int X[], int Y[]) {
	n = N;
    S.insert(1);
	for(int i=1; i<=n; i++) {
		x[i] = X[i-1]; y[i] = Y[i-1];
        if(x[i] != 1) S.insert(i);
	}
    A.bd(1, 1, n);
    B.bd(1, 1, n);
    
	return calc();
}

int updateX(int pos, int val) {	
    pos++;
    if(x[pos] != 1 && val == 1) S.erase(pos); 
    if(x[pos] == 1 && val != 1) S.insert(pos);
    S.insert(1);
    
	x[pos] = val; 
    // upd segtree X
    A.upd(1, 1, n, pos, val);
    
	return calc();
}

int updateY(int pos, int val) {
    pos++;
	y[pos] = val; 
    // upd segtree Y
    B.upd(1, 1, n, pos, val);
    
	return calc();
}

Compilation message

horses.cpp: In member function 'long long int seg::que(int, int, int, int, int)':
horses.cpp:37:42: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   37 |  ll que(int id, int l, int r, int x, int y){
      |                                      ~~~~^
horses.cpp:24:13: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |             ^
horses.cpp:37:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   37 |  ll que(int id, int l, int r, int x, int y){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In member function 'long long int seg::upd(int, int, int, int, long long int)':
horses.cpp:42:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   42 |  ll upd(int id, int l, int r, int x, ll p){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In member function 'long long int segtree::que(int, int, int, int, int)':
horses.cpp:60:42: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   60 |  ll que(int id, int l, int r, int x, int y){
      |                                      ~~~~^
horses.cpp:24:13: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |             ^
horses.cpp:60:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   60 |  ll que(int id, int l, int r, int x, int y){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In member function 'long long int segtree::upd(int, int, int, int, long long int)':
horses.cpp:65:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   65 |  ll upd(int id, int l, int r, int x, ll p){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In function 'int calc()':
horses.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i=0;i<cand.size();i++) {
      |                  ~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 39368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4528 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4548 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 4 ms 4444 KB Output is correct
24 Correct 3 ms 4444 KB Output is correct
25 Correct 3 ms 4664 KB Output is correct
26 Correct 3 ms 4444 KB Output is correct
27 Correct 3 ms 4444 KB Output is correct
28 Correct 3 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 3 ms 4444 KB Output is correct
31 Correct 2 ms 4444 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Runtime error 23 ms 18872 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4284 KB Output is correct
4 Correct 1 ms 4456 KB Output is correct
5 Correct 1 ms 4456 KB Output is correct
6 Correct 1 ms 4456 KB Output is correct
7 Correct 1 ms 4556 KB Output is correct
8 Correct 1 ms 4456 KB Output is correct
9 Correct 1 ms 4456 KB Output is correct
10 Correct 1 ms 4456 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4548 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 3 ms 4444 KB Output is correct
24 Correct 3 ms 4444 KB Output is correct
25 Correct 3 ms 4560 KB Output is correct
26 Correct 3 ms 4440 KB Output is correct
27 Correct 3 ms 4444 KB Output is correct
28 Correct 3 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 3 ms 4652 KB Output is correct
31 Correct 2 ms 4444 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Runtime error 56 ms 40220 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -