oj.uz

Submission #87983

# Submission time Handle Problem Language Result Execution time Memory
87983 2018-12-03T10:53:51 Z Pajaraja Horses (IOI15_horses) C++17
100 / 100
 1167 ms 91740 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define MOD 1000000007
long long y[500040],x[500040],pr,seg[2][2000040],pb[32],td;
void upd(int l,int r,int val,int k,int poz,int ind)
{
	if(l==r)
	{
		seg[k][ind]=val;
		return;
	}
	int s=(l+r)/2;
	if(s>=poz) upd(l,s,val,k,poz,2*ind);
	else upd(s+1,r,val,k,poz,2*ind+1);
	seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
}
long long find(int lt,int rt,int l,int r,int k,int ind)
{
	if(l>rt||r<lt) return 0;
	if(l>=lt&&r<=rt) return seg[k][ind];
	int s=(l+r)/2;
	return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
}
long long mmi(long long b,int exp)
{
	if(exp==0) return 1;
	long long r=mmi(b,exp/2);
	r=(r*r)%MOD;
	if(exp%2==0) return r;
	return (r*b)%MOD;
}
int n,cnt;
int resi()
{
	bool gdd=false;
	if(cnt<32) 
	{
	    pb[cnt]=-1;
	    gdd=true;
	    cnt++;
	}
	long long prt=1;
	int ind=0,prev=n;
	for(int i=0;i<cnt;i++)
	{
		long long r=find(pb[i],prev-1,0,n-1,1,1);
		if(r>prt)
		{
		    prt=r;
		    ind=i;
		}
		if(pb[i]!=-1) prt*=x[pb[i]];
		prev=pb[i];
		if(prt>MOD) break;
	}
	prt=1;
	for(int i=0;i<ind;i++) if(pb[i]!=-1) prt*=x[pb[i]];
	prev=(ind==0?n:pb[ind-1]);
	long long r=find(pb[ind],prev-1,0,n-1,1,1);
	if(gdd) cnt--;
	return (((pr*mmi(prt,MOD-2))%MOD)*r)%MOD;
}
int init(int N, int X[], int Y[]) 
{
	n=N;
	pr=1;
	td=0;
	for(int i=0;i<n;i++)
	{
	    x[i]=X[i];
	    upd(0,n-1,x[i],0,i,1);
	}
	for(int i=0;i<n;i++) 
	{
	    y[i]=Y[i];
	    upd(0,n-1,y[i],1,i,1);
	}
	for(int i=0;i<n;i++) pr=(pr*x[i])%MOD;
	for(int i=n-1;i>=0;i--) if(x[i]>1)
	{
		pb[cnt]=i;
		cnt++;
		if(cnt==32) break;
	}
	for(int i=n-1;i>=0;i--) if(x[i]>1) td++;
	return resi();
}
int binarna(int l,int r,int k)
{
	if(l==r) return l;
	int s=(l+r+1)/2;
	if(find(s,k,0,n-1,0,1)>1) return binarna(s,r,k);
	return binarna(l,s-1,k);
}
int updateX(int pos, int val) 
{
	pr=(pr*mmi(x[pos],MOD-2))%MOD;
	long long tmp,r=x[pos];
	x[pos]=val;
	pr=(pr*val)%MOD;
	upd(0,n-1,val,0,pos,1);
	if(r==1 && val>1)
	{
		td++;
		int d=33,prev=n;
		for(int i=0;i<cnt;i++)
		{
			if(pos>pb[i] && pos<prev)
			{
				d=i;
				break;
			}
			prev=pb[i];
		}
		for(int i=31;i>d;i--) pb[i]=pb[i-1];
		if(d==33&&cnt<32) pb[cnt]=pos;
		pb[d]=pos;
		cnt=fmin(32,td);
	}
	if(r>1&&val==1)
	{
		td--;
		int d=33;
		for(int i=0;i<cnt;i++)
		{
			if(pb[i]==pos)
			{
				d=i;
				break;
			}
		}
		for(int i=d;i<cnt-1;i++) pb[i]=pb[i+1];
		if(td>=32&&d!=33) pb[31]=binarna(0,pb[30]-1,pb[30]-1);
		cnt=fmin(32,td);
	}
	return resi();
}
int updateY(int pos, int val) 
{
	upd(0,n-1,val,1,pos,1);
	return resi();
}
//QED

Compilation message

horses.cpp: In function 'void upd(int, int, int, int, int, int)':
horses.cpp:15:31: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
                   ~~~~~~~~~~~~^
horses.cpp:15:47: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
                                 ~~~~~~~~~~~~~~^
horses.cpp:15:18: warning: conversion to 'long long int' from 'double' may alter its value [-Wfloat-conversion]
  seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
              ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'long long int find(int, int, int, int, int, int)':
horses.cpp:22:18: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
              ~~~~^~~~~~~~~~~~~~~~~~~
horses.cpp:22:42: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
                                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:22:13: warning: conversion to 'long long int' from 'double' may alter its value [-Wfloat-conversion]
  return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int resi()':
horses.cpp:46:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   long long r=find(pb[i],prev-1,0,n-1,1,1);
                    ~~~~^
horses.cpp:53:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   prev=pb[i];
        ~~~~^
horses.cpp:58:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  prev=(ind==0?n:pb[ind-1]);
       ~~~~~~~^~~~~~~~~~~~~
horses.cpp:59:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  long long r=find(pb[ind],prev-1,0,n-1,1,1);
                   ~~~~~~^
horses.cpp:61:38: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (((pr*mmi(prt,MOD-2))%MOD)*r)%MOD;
                                      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
      upd(0,n-1,x[i],0,i,1);
                ~~~^
horses.cpp:76:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
      upd(0,n-1,y[i],1,i,1);
                ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:113:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    prev=pb[i];
         ~~~~^
horses.cpp:118:17: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   cnt=fmin(32,td);
                 ^
horses.cpp:118:11: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
   cnt=fmin(32,td);
       ~~~~^~~~~~~
horses.cpp:133:44: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(td>=32&&d!=33) pb[31]=binarna(0,pb[30]-1,pb[30]-1);
                                      ~~~~~~^~
horses.cpp:133:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(td>=32&&d!=33) pb[31]=binarna(0,pb[30]-1,pb[30]-1);
                                               ~~~~~~^~
horses.cpp:134:17: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   cnt=fmin(32,td);
                 ^
horses.cpp:134:11: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
   cnt=fmin(32,td);
       ~~~~^~~~~~~
horses.cpp:98:12: warning: unused variable 'tmp' [-Wunused-variable]
  long long tmp,r=x[pos];
            ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 772 KB Output is correct
2 Correct 3 ms 772 KB Output is correct
3 Correct 2 ms 772 KB Output is correct
4 Correct 2 ms 772 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 2 ms 772 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 3 ms 772 KB Output is correct
11 Correct 2 ms 772 KB Output is correct
12 Correct 2 ms 772 KB Output is correct
13 Correct 2 ms 772 KB Output is correct
14 Correct 2 ms 772 KB Output is correct
15 Correct 2 ms 772 KB Output is correct
16 Correct 2 ms 776 KB Output is correct
17 Correct 2 ms 780 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 2 ms 788 KB Output is correct
20 Correct 2 ms 792 KB Output is correct
21 Correct 2 ms 796 KB Output is correct
22 Correct 2 ms 800 KB Output is correct
23 Correct 4 ms 904 KB Output is correct
24 Correct 4 ms 944 KB Output is correct
25 Correct 4 ms 988 KB Output is correct
26 Correct 4 ms 988 KB Output is correct
27 Correct 24 ms 988 KB Output is correct
28 Correct 5 ms 988 KB Output is correct
29 Correct 4 ms 988 KB Output is correct
30 Correct 5 ms 988 KB Output is correct
31 Correct 6 ms 1024 KB Output is correct
32 Correct 7 ms 1032 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 34044 KB Output is correct
2 Correct 450 ms 44636 KB Output is correct
3 Correct 500 ms 48252 KB Output is correct
4 Correct 450 ms 56020 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 56020 KB Output is correct
2 Correct 2 ms 56020 KB Output is correct
3 Correct 2 ms 56020 KB Output is correct
4 Correct 2 ms 56020 KB Output is correct
5 Correct 2 ms 56020 KB Output is correct
6 Correct 2 ms 56020 KB Output is correct
7 Correct 2 ms 56020 KB Output is correct
8 Correct 2 ms 56020 KB Output is correct
9 Correct 2 ms 56020 KB Output is correct
10 Correct 2 ms 56020 KB Output is correct
11 Correct 2 ms 56020 KB Output is correct
12 Correct 2 ms 56020 KB Output is correct
13 Correct 2 ms 56020 KB Output is correct
14 Correct 2 ms 56020 KB Output is correct
15 Correct 3 ms 56020 KB Output is correct
16 Correct 2 ms 56020 KB Output is correct
17 Correct 2 ms 56020 KB Output is correct
18 Correct 3 ms 56020 KB Output is correct
19 Correct 2 ms 56020 KB Output is correct
20 Correct 2 ms 56020 KB Output is correct
21 Correct 2 ms 56020 KB Output is correct
22 Correct 2 ms 56020 KB Output is correct
23 Correct 4 ms 56020 KB Output is correct
24 Correct 4 ms 56020 KB Output is correct
25 Correct 4 ms 56020 KB Output is correct
26 Correct 3 ms 56020 KB Output is correct
27 Correct 7 ms 56020 KB Output is correct
28 Correct 5 ms 56020 KB Output is correct
29 Correct 5 ms 56020 KB Output is correct
30 Correct 5 ms 56020 KB Output is correct
31 Correct 6 ms 56020 KB Output is correct
32 Correct 7 ms 56020 KB Output is correct
33 Correct 273 ms 59160 KB Output is correct
34 Correct 274 ms 63160 KB Output is correct
35 Correct 312 ms 65724 KB Output is correct
36 Correct 290 ms 65784 KB Output is correct
37 Correct 348 ms 65784 KB Output is correct
38 Correct 285 ms 65784 KB Output is correct
39 Correct 272 ms 65812 KB Output is correct
40 Correct 316 ms 65812 KB Output is correct
41 Correct 309 ms 65876 KB Output is correct
42 Correct 334 ms 65876 KB Output is correct
43 Correct 270 ms 65876 KB Output is correct
44 Correct 269 ms 65876 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 65876 KB Output is correct
2 Correct 2 ms 65876 KB Output is correct
3 Correct 3 ms 65876 KB Output is correct
4 Correct 2 ms 65876 KB Output is correct
5 Correct 2 ms 65876 KB Output is correct
6 Correct 2 ms 65876 KB Output is correct
7 Correct 2 ms 65876 KB Output is correct
8 Correct 2 ms 65876 KB Output is correct
9 Correct 3 ms 65876 KB Output is correct
10 Correct 2 ms 65876 KB Output is correct
11 Correct 0 ms 65876 KB Output is correct
12 Correct 2 ms 65876 KB Output is correct
13 Correct 2 ms 65876 KB Output is correct
14 Correct 2 ms 65876 KB Output is correct
15 Correct 2 ms 65876 KB Output is correct
16 Correct 2 ms 65876 KB Output is correct
17 Correct 2 ms 65876 KB Output is correct
18 Correct 2 ms 65876 KB Output is correct
19 Correct 2 ms 65876 KB Output is correct
20 Correct 3 ms 65876 KB Output is correct
21 Correct 3 ms 65876 KB Output is correct
22 Correct 2 ms 65876 KB Output is correct
23 Correct 4 ms 65876 KB Output is correct
24 Correct 4 ms 65876 KB Output is correct
25 Correct 4 ms 65876 KB Output is correct
26 Correct 4 ms 65876 KB Output is correct
27 Correct 7 ms 65876 KB Output is correct
28 Correct 5 ms 65876 KB Output is correct
29 Correct 4 ms 65876 KB Output is correct
30 Correct 5 ms 65876 KB Output is correct
31 Correct 6 ms 65876 KB Output is correct
32 Correct 7 ms 65876 KB Output is correct
33 Correct 980 ms 66672 KB Output is correct
34 Correct 469 ms 72340 KB Output is correct
35 Correct 514 ms 76112 KB Output is correct
36 Correct 461 ms 83616 KB Output is correct
37 Correct 277 ms 86516 KB Output is correct
38 Correct 276 ms 90336 KB Output is correct
39 Correct 312 ms 90648 KB Output is correct
40 Correct 291 ms 90756 KB Output is correct
41 Correct 347 ms 90756 KB Output is correct
42 Correct 278 ms 90756 KB Output is correct
43 Correct 272 ms 90756 KB Output is correct
44 Correct 314 ms 90876 KB Output is correct
45 Correct 308 ms 90876 KB Output is correct
46 Correct 330 ms 90876 KB Output is correct
47 Correct 259 ms 90876 KB Output is correct
48 Correct 260 ms 90876 KB Output is correct
49 Correct 444 ms 91468 KB Output is correct
50 Correct 431 ms 91576 KB Output is correct
51 Correct 617 ms 91576 KB Output is correct
52 Correct 413 ms 91576 KB Output is correct
53 Correct 1167 ms 91576 KB Output is correct
54 Correct 545 ms 91576 KB Output is correct
55 Correct 458 ms 91576 KB Output is correct
56 Correct 770 ms 91612 KB Output is correct
57 Correct 844 ms 91632 KB Output is correct
58 Correct 1094 ms 91740 KB Output is correct
59 Correct 261 ms 91740 KB Output is correct