답안 #56745 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56745	2018-07-12T11:26:44 Z	Bodo171	말 (IOI15_horses)	C++14	37 / 100	935 ms	73548 KB

horses

#include "horses.h"
#include <iostream>
#include <set>
#include <climits>
using namespace std;
const int nmax=500005;
set<int> s;
set<int>::iterator it;
const long long mod=1000*1000*1000+7;
long long pr[4*nmax];
int arb[4*nmax];
int bun[nmax],v[nmax];
int mx,x,y,value,poz,st,dr,n,lg,ok,lst;
long long ans;
void U(int nod,int l,int r)
{
    if(l==r)
    {
        pr[nod]=value;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) U(2*nod,l,m);
    else U(2*nod+1,m+1,r);
    pr[nod]=(1LL*pr[2*nod]*pr[2*nod+1])%mod;
}
void Q(int nod,int l,int r)
{
    if(st<=l&&r<=dr)
    {
        ans=(1LL*ans*pr[nod])%mod;
        return;
    }
    int m=(l+r)/2;
    if(st<=m) Q(2*nod,l,m);
    if(m<dr) Q(2*nod+1,m+1,r);
}
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod]=value;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r)
{
    if(st<=l&&r<=dr)
    {
        mx=max(mx,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m);
    if(m<dr) query(2*nod+1,m+1,r);
}
int qry(int S,int D)
{
    st=S;dr=D;mx=0;
    query(1,1,n);
    return mx;
}
int get_mx()
{
    long long opt=0;
    it=s.lower_bound(n+1);
    lg=32;mx=0;ok=1;poz=n;
    for(int i=1;i<=lg&&it!=s.begin()&&ok;i++)
    {
        it--;
        x=v[(*it)-1];y=bun[(*it)];
        if(y>mx) mx=y,poz=(*it),opt=y;
        if(mx!=0&&x>INT_MAX/mx) ok=0;
        else mx*=x;
    }
    st=1;dr=poz;ans=1;
    Q(1,1,n);
    ans=(1LL*ans*opt)%mod;
    return ans;
}
int init(int N, int X[], int Y[]) {
    n=N;
    for(int i=0;i<N;i++)
    {
        poz=i+1;value=X[i];v[i]=X[i];
        U(1,1,n);
    }
    for(int i=0;i<N;i++)
    {
        poz=i+1;value=Y[i];
        update(1,1,n);
    }
    s.insert(n+1);lst=N;
    for(int i=N-1;i>=0;i--)
       if(X[i]!=1)
    {
        s.insert(i+1);
        bun[i+1]=qry(i+1,lst);
        lst=i;
    }
    if(s.find(1)==s.end())
    {
        bun[1]=qry(1,n);
        s.insert(1);
    }
	return get_mx();
}

int updateX(int pos, int val) {
    poz=pos+1;value=val;
    if(v[poz-1]!=1)
    {
        s.erase(poz);
    }
    U(1,1,n);
    v[poz-1]=val;
    if(val!=1)
    {
        s.insert(poz);
    }
    bun[poz]=qry(poz,(*s.upper_bound(poz))-1);
    if(s.find(1)==s.end())
    {
        bun[1]=qry(1,n);
        s.insert(1);
    }
	return get_mx();
}

int updateY(int pos, int val) {

    poz=pos+1;value=val;
    update(1,1,n);
    it=s.upper_bound(poz);
    if(it!=s.begin())
    {
        it--;
        bun[(*it)]=qry((*it),(*s.upper_bound((*it)))-1);
    }
	return get_mx();
}

Compilation message

horses.cpp: In function 'int get_mx()':
horses.cpp:83:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ans;
            ^~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	572 KB	Output is correct
2	Correct	3 ms	664 KB	Output is correct
3	Correct	2 ms	664 KB	Output is correct
4	Correct	2 ms	664 KB	Output is correct
5	Correct	2 ms	756 KB	Output is correct
6	Correct	2 ms	756 KB	Output is correct
7	Correct	3 ms	756 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	3 ms	816 KB	Output is correct
10	Correct	2 ms	836 KB	Output is correct
11	Correct	2 ms	840 KB	Output is correct
12	Correct	3 ms	844 KB	Output is correct
13	Correct	2 ms	848 KB	Output is correct
14	Correct	2 ms	852 KB	Output is correct
15	Correct	2 ms	856 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	2 ms	864 KB	Output is correct
18	Correct	2 ms	908 KB	Output is correct
19	Correct	2 ms	912 KB	Output is correct
20	Correct	2 ms	916 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	920 KB	Output is correct
2	Correct	3 ms	924 KB	Output is correct
3	Correct	2 ms	928 KB	Output is correct
4	Correct	2 ms	932 KB	Output is correct
5	Correct	2 ms	932 KB	Output is correct
6	Correct	2 ms	944 KB	Output is correct
7	Correct	2 ms	944 KB	Output is correct
8	Correct	2 ms	948 KB	Output is correct
9	Correct	2 ms	952 KB	Output is correct
10	Correct	2 ms	1084 KB	Output is correct
11	Correct	2 ms	1084 KB	Output is correct
12	Correct	2 ms	1084 KB	Output is correct
13	Correct	3 ms	1084 KB	Output is correct
14	Correct	2 ms	1084 KB	Output is correct
15	Correct	2 ms	1084 KB	Output is correct
16	Correct	3 ms	1084 KB	Output is correct
17	Correct	3 ms	1084 KB	Output is correct
18	Correct	3 ms	1084 KB	Output is correct
19	Correct	3 ms	1084 KB	Output is correct
20	Correct	3 ms	1084 KB	Output is correct
21	Correct	3 ms	1084 KB	Output is correct
22	Incorrect	3 ms	1084 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	673 ms	49604 KB	Output is correct
2	Correct	885 ms	62300 KB	Output is correct
3	Correct	868 ms	65928 KB	Output is correct
4	Correct	935 ms	73548 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	73548 KB	Output is correct
2	Correct	3 ms	73548 KB	Output is correct
3	Correct	3 ms	73548 KB	Output is correct
4	Correct	3 ms	73548 KB	Output is correct
5	Correct	3 ms	73548 KB	Output is correct
6	Correct	2 ms	73548 KB	Output is correct
7	Correct	3 ms	73548 KB	Output is correct
8	Correct	2 ms	73548 KB	Output is correct
9	Correct	4 ms	73548 KB	Output is correct
10	Correct	2 ms	73548 KB	Output is correct
11	Correct	2 ms	73548 KB	Output is correct
12	Correct	2 ms	73548 KB	Output is correct
13	Correct	2 ms	73548 KB	Output is correct
14	Correct	3 ms	73548 KB	Output is correct
15	Correct	3 ms	73548 KB	Output is correct
16	Correct	3 ms	73548 KB	Output is correct
17	Correct	3 ms	73548 KB	Output is correct
18	Correct	2 ms	73548 KB	Output is correct
19	Correct	2 ms	73548 KB	Output is correct
20	Correct	2 ms	73548 KB	Output is correct
21	Correct	3 ms	73548 KB	Output is correct
22	Incorrect	3 ms	73548 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	73548 KB	Output is correct
2	Correct	2 ms	73548 KB	Output is correct
3	Correct	3 ms	73548 KB	Output is correct
4	Correct	3 ms	73548 KB	Output is correct
5	Correct	1 ms	73548 KB	Output is correct
6	Correct	2 ms	73548 KB	Output is correct
7	Correct	3 ms	73548 KB	Output is correct
8	Correct	2 ms	73548 KB	Output is correct
9	Correct	2 ms	73548 KB	Output is correct
10	Correct	3 ms	73548 KB	Output is correct
11	Correct	3 ms	73548 KB	Output is correct
12	Correct	2 ms	73548 KB	Output is correct
13	Correct	3 ms	73548 KB	Output is correct
14	Correct	3 ms	73548 KB	Output is correct
15	Correct	3 ms	73548 KB	Output is correct
16	Correct	3 ms	73548 KB	Output is correct
17	Correct	3 ms	73548 KB	Output is correct
18	Correct	2 ms	73548 KB	Output is correct
19	Correct	3 ms	73548 KB	Output is correct
20	Correct	3 ms	73548 KB	Output is correct
21	Correct	2 ms	73548 KB	Output is correct
22	Incorrect	3 ms	73548 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

답안 #56745

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0