oj.uz

Submission #702760

# Submission time Handle Problem Language Result Execution time Memory
702760 2023-02-25T05:25:53 Z lukameladze Horses (IOI15_horses) C++14
17 / 100
 715 ms 64936 KB 
# include "horses.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair <ll, ll>

const int NN = 5e5 + 5, inf = 2e9, mod = 1e9 + 7; 
long long n, x[NN],y[NN],tree_ml[4 * NN];
pii tree_mx[4 * NN]; 
long long merge_ml(ll a, ll b) {
    return (a * b) % mod;
}
pii merge_mx(pii a, pii b) {
    return max(a, b);
}
void build(int node, int le, int ri) {
    if (le == ri) {
        tree_ml[node] = x[le];
        tree_mx[node] = {y[le], le};
        return ;
    }
    int mid = (le + ri) / 2;
    build(2 * node, le, mid);
    build(2 * node + 1, mid + 1, ri);
    tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
    tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
void update(int node, int le, int ri, int idx, ll val, int ty) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        if (ty == 0) tree_ml[node] = x[le];
        else tree_mx[node] = {y[le], le};
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node,le, mid,idx,val,ty);
    update(2 * node + 1, mid + 1, ri, idx,val,ty);
    tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
    tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
ll get_ml(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start || start > end) return 1LL;
    if (le >= start && ri <= end) return tree_ml[node];
    int mid = (le + ri) / 2;
    return merge_ml(get_ml(2 * node, le, mid, start,end), get_ml(2 * node + 1, mid + 1, ri, start, end));
}
pii get_mx(int node, int le, int ri, int start, int end) {
   if (le > end || ri < start || start > end) return {-1e9, 0LL};
   if (le >= start && ri <= end) return tree_mx[node];
   int mid = (le + ri) / 2;
   return merge_mx(get_mx(2 * node, le, mid,start,end), get_mx(2 * node + 1, mid + 1, ri, start, end)); 
}
set <ll> s;
ll go() {
    auto it = --s.end(); // n + 1
    auto it1 = it; it--;
    int cur_mx = 1, cnt = 0, optid = n;
    while (true) {
        cnt++;
        int st_y = (*it); int nd_y = (*it1) - 1;
        if (st_y == 0) st_y++;
        int mx_y = get_mx(1,1,n,st_y, nd_y).f;
        if (mx_y > cur_mx) {
            optid = get_mx(1,1,n, st_y, nd_y).s;
            cur_mx = mx_y;
        }
        cur_mx *= x[st_y];
        if (it1 == s.begin() || cnt > 32 || cur_mx > inf) break;
        it--; it1--;
    }
    return (get_ml(1,1,n,1,optid) * y[optid]) % mod;
}
int init(int N, int X[], int Y[]) {
    n = N;
    x[0] = 1; y[0] = 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);
    }
    s.insert(0); s.insert(n + 1);
    build(1, 1, n);
	return go();
}
 
int updateX(int pos, int val) {	
    pos++;
    if (x[pos] != 1) {
        s.erase(pos);
    }
    x[pos] = val;
    update(1,1,n, pos,val,0);
    if (x[pos] != 1) s.insert(pos);
    return go();
}
 
int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
    update(1,1,n, pos,val, 1);
    return go();
}
/*
main() {
    int N;
    cin>>N;
	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
 
	for (int i = 0; i < N; i++) {
		cin>>X[i];
	}
 
	for (int i = 0; i < N; i++) {
		cin>>Y[i];
	}	
 
	cout<<init(N,X,Y)<<"\n";
    int M;
	cin>>M;
 
	for (int i = 0; i < M; i++) {
		int type; cin>>type;
		int pos; cin>>pos;
		int val; cin>>val; 
 
		if (type == 1) {
			cout<<updateX(pos,val)<<"\n";
		} else if (type == 2) {
			cout<<updateY(pos,val)<<"\n";
		}
	}
 
	return 0;
}*/

Compilation message

horses.cpp: In function 'long long int go()':
horses.cpp:59:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   59 |     int cur_mx = 1, cnt = 0, optid = n;
      |                                      ^
horses.cpp:62:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |         int st_y = (*it); int nd_y = (*it1) - 1;
      |                    ~^~~~
horses.cpp:62:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |         int st_y = (*it); int nd_y = (*it1) - 1;
      |                                      ~~~~~~~^~~
horses.cpp:64:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   64 |         int mx_y = get_mx(1,1,n,st_y, nd_y).f;
      |                               ^
horses.cpp:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define f first
      |           ^
horses.cpp:64:45: note: in expansion of macro 'f'
   64 |         int mx_y = get_mx(1,1,n,st_y, nd_y).f;
      |                                             ^
horses.cpp:66:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   66 |             optid = get_mx(1,1,n, st_y, nd_y).s;
      |                                ^
horses.cpp:5:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    5 | #define s second
      |           ^
horses.cpp:66:47: note: in expansion of macro 's'
   66 |             optid = get_mx(1,1,n, st_y, nd_y).s;
      |                                               ^
horses.cpp:69:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |         cur_mx *= x[st_y];
      |         ~~~~~~~^~~~~~~~~~
horses.cpp:73:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |     return (get_ml(1,1,n,1,optid) * y[optid]) % mod;
      |                        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:83:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |     build(1, 1, n);
      |                 ^
horses.cpp:84:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return go();
      |         ~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |     update(1,1,n, pos,val,0);
      |                ^
horses.cpp:95:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |     return go();
      |            ~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:101:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |     update(1,1,n, pos,val, 1);
      |                ^
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |     return go();
      |            ~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 715 ms 64936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 312 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Incorrect 0 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -