oj.uz

Submission #641119

# Submission time Handle Problem Language Result Execution time Memory
641119 2022-09-16T03:12:47 Z ymm Horses (IOI15_horses) C++17
17 / 100
 468 ms 55944 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

typedef __float128 fl;
static const int N = 1<<19;
static const int mod = 1e9+7;
static int n;

struct {
	fl mxf;
	fl lzf;
	int mxi;
	int lzi;
} __attribute__((packed)) seg[N<<1];

static void upd(int i, fl xf, int xi)
{
	seg[i].mxf += xf;
	seg[i].lzf += xf;
	seg[i].mxi = ((ll)seg[i].mxi * xi) % mod;
	seg[i].lzi = ((ll)seg[i].lzi * xi) % mod;
}

static void down(int i)
{
	upd(2*i+1, seg[i].lzf, seg[i].lzi);
	upd(2*i+2, seg[i].lzf, seg[i].lzi);
	seg[i].lzf = 0;
	seg[i].lzi = 1;
}

static void up(int i)
{
	if (seg[2*i+1].mxf > seg[2*i+2].mxf)
		seg[i] = seg[2*i+1];
	else
		seg[i] = seg[2*i+2];
}

static void add(int l, int r, fl xf, int xi, int i=0, int b=0, int e=n)
{
	if (l <= b && e <= r)
		return upd(i, xf, xi);
	if (r <= b || e <= l)
		return;
	down(i);
	add(l,r,xf,xi,2*i+1,b,(b+e)/2);
	add(l,r,xf,xi,2*i+2,(b+e)/2,e);
	up(i);
}

static void seg_init(fl xf[], int xi[], int i=0, int b=0, int e=n)
{
	if (e-b == 1) {
		seg[i] = {xf[b], 0, xi[b], 1};
		return;
	}
	seg_init(xf,xi,2*i+1,b,(b+e)/2);
	seg_init(xf,xi,2*i+2,(b+e)/2,e);
	up(i);
}

fl xf[N];
int xi[N];
int *X, *Y;

int init(int n, int X[], int Y[]) {
	xf[0] = log2((long double)X[0]); Loop (i,1,n) xf[i] = xf[i-1]+log2((double)X[i]);
	Loop (i,0,n) xf[i] += log2((long double)Y[i]);
	xi[0] = X[0]; Loop (i,1,n) xi[i] = ((ll)xi[i-1] * X[i]) % mod;
	Loop (i,0,n) xi[i] = ((ll)xi[i] * Y[i]) % mod;
	::X = X;
	::Y = Y;
	::n = n;
	seg_init(xf, xi);
	return seg[0].mxi;
}

static ll mpow(ll x, ll y){ll ans=1;while(y){ans=y&1?ans*x%mod:ans;x=x*x%mod;y>>=1;}return ans;}

int updateX(int pos, int val) {	
	add(pos, n, -log2((long double)X[pos]), mpow(X[pos], mod-2));
	X[pos] = val;
	add(pos, n, log2((long double)X[pos]), X[pos]);
	return seg[0].mxi;
}

int updateY(int pos, int val) {
	add(pos, pos+1, -log2((long double)Y[pos]), mpow(Y[pos], mod-2));
	Y[pos] = val;
	add(pos, pos+1, log2((long double)Y[pos]), Y[pos]);
	return seg[0].mxi;
}

Compilation message

horses.cpp: In function 'void upd(int, fl, int)':
horses.cpp:26:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |  seg[i].mxi = ((ll)seg[i].mxi * xi) % mod;
      |               ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:27:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   27 |  seg[i].lzi = ((ll)seg[i].lzi * xi) % mod;
      |               ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:73:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   73 | int init(int n, int X[], int Y[]) {
      |                          ~~~~^~~
horses.cpp:71:10: note: shadowed declaration is here
   71 | int *X, *Y;
      |          ^
horses.cpp:73:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   73 | int init(int n, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:71:6: note: shadowed declaration is here
   71 | int *X, *Y;
      |      ^
horses.cpp:73:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   73 | int init(int n, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:13:12: note: shadowed declaration is here
   13 | static int n;
      |            ^
horses.cpp:76:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   76 |  xi[0] = X[0]; Loop (i,1,n) xi[i] = ((ll)xi[i-1] * X[i]) % mod;
      |                                     ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:77:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   77 |  Loop (i,0,n) xi[i] = ((ll)xi[i] * Y[i]) % mod;
      |                       ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:88:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   88 |  add(pos, n, -log2((long double)X[pos]), mpow(X[pos], mod-2));
      |                                          ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   95 |  add(pos, pos+1, -log2((long double)Y[pos]), mpow(Y[pos], mod-2));
      |                                              ~~~~^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 260 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 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 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 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 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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