oj.uz

Submission #747214

# Submission time Handle Problem Language Result Execution time Memory
747214 2023-05-24T00:09:48 Z Abrar_Al_Samit Horses (IOI15_horses) C++17
20 / 100
 616 ms 57276 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

const int nax = 5e5 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9;
long long x[nax], y[nax];
int n;

long long mul(long long a, long long b) {
	return (a * b) % mod;
}
long long quickpow(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ret;
}


struct BIT {
	long long b[nax];
	BIT() {
		for(int i=0; i<nax; ++i) {
			b[i] = 1;
		}
	}

	void update(int p, int val) {
		while(p<nax) {
			b[p] = mul(b[p], val);
			p += p&-p;
		}
	}
	long long query(int p) {
		long long ret = 1;
		while(p) {
			ret = mul(ret, b[p]);
			p -= p&-p;
		}
		return ret;
	}

} fen;
int seg[1<<20];
void update(int pos, int val, int l=1, int r=n, int v=1) {
	if(l==r) {
		seg[v] = val;
		return;
	}
	int mid = (l+r)/2;
	if(pos<=mid) update(pos, val, l, mid, v*2);
	else update(pos, val, mid+1, r, v*2+1);
	seg[v] = max(seg[v*2], seg[v*2+1]);
}
int query(int L, int R, int l=1, int r=n, int v=1) {
	if(l>=L && r<=R) return seg[v];
	if(l>R || r<L) return 0;
	int mid = (l+r)/2;
	return max(query(L, R, l, mid, v*2), query(L, R, mid+1, r, v*2+1));
}

set<int>nonone;
int get() {
    long long ret = 0;
    int next_big = n;

    int t = 30;
    long long later = 0;
    for(auto it = prev(nonone.end()); t>0 && later<=MX; --it, --t) {
        long long price = query(*it+1, next_big);
        if(price > later) {
            later = price;

            ret = (price * fen.query(*it+1)) % mod;
        }

        if(it==nonone.begin()) break;
        later *= x[*it];
    }

    return ret;
}
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0; i<n; ++i) {
		x[i] = X[i], y[i] = Y[i];
		fen.update(i+1, x[i]);
		update(i+1, y[i]);

		if(x[i]>1) nonone.insert(i);
	}
	return get();
}

int updateX(int pos, int val) {	
	fen.update(pos+1, quickpow(x[pos], mod-2));
	fen.update(pos+1, val);

	if(x[pos]==1 && val>1) {
		nonone.insert(pos);
	} else if(x[pos]>1 && val==1) {
		nonone.erase(pos);
	} 

	x[pos] = val;
    nonone.insert(0);

	return get();
}

int updateY(int pos, int val) {
	update(pos+1, val);
	y[pos] = val;

	return get();
}

Compilation message

horses.cpp: In function 'int get()':
horses.cpp:86:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |     return ret;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:92:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |   fen.update(i+1, x[i]);
      |                   ~~~^
horses.cpp:93:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |   update(i+1, y[i]);
      |               ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:101:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |  fen.update(pos+1, quickpow(x[pos], mod-2));
      |                    ~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4224 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Runtime error 6 ms 8276 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Runtime error 7 ms 8332 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 48348 KB Output is correct
2 Correct 301 ms 57276 KB Output is correct
3 Correct 402 ms 48276 KB Output is correct
4 Correct 278 ms 52044 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4228 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Runtime error 6 ms 8324 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4228 KB Output is correct
5 Runtime error 6 ms 8276 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -