oj.uz

답안 #621350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
621350 2022-08-03T17:56:01 Z A_D 말 (IOI15_horses) C++14
100 / 100
 1415 ms 64744 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+100;
const long long MOD=1e9+7;
const long long L=32;
long long x[N];
long long y[N];
set<int> st;
int n;
vector<int> vec;
long long seg[4*N];
long long seg2[4*N];

void build(int p,int s,int e)
{
    if(s==e){
        seg[p]=y[s];
        seg2[p]=x[s];
        return;
    }
    int mid=(s+e)/2;
    build(p*2,s,mid);
    build(p*2+1,mid+1,e);
    seg[p]=max(seg[p*2],seg[p*2+1]);
    seg2[p]=(seg2[p*2]*seg2[p*2+1])%MOD;
}

void update(int p,int s,int e,int i,int val)
{
    if(s==e){
        seg[p]=val;
        return;
    }
    int mid=(s+e)/2;
    if(i<=mid){
        update(p*2,s,mid,i,val);
    }
    else{
        update(p*2+1,mid+1,e,i,val);
    }
    seg[p]=max(seg[p*2],seg[p*2+1]);
}

void update2(int p,int s,int e,int i,int val)
{
    if(s==e){
        seg2[p]=val;
        return;
    }
    int mid=(s+e)/2;
    if(i<=mid){
        update2(p*2,s,mid,i,val);
    }
    else{
        update2(p*2+1,mid+1,e,i,val);
    }
    seg2[p]=(seg2[p*2]*seg2[p*2+1])%MOD;
}

long long get(int p,int s,int e,int a,int b)
{
    if(a<=s&&e<=b){
        return seg[p];
    }
    if(s>b||e<a)return 1;
    int mid=(s+e)/2;
    return max(get(p*2,s,mid,a,b),get(p*2+1,mid+1,e,a,b));
}

long long get2(int p,int s,int e,int a,int b)
{
    if(b==-1)return 1;
    if(a<=s&&e<=b){
        return seg2[p];
    }
    if(s>b||e<a)return 1;
    int mid=(s+e)/2;
    return (get2(p*2,s,mid,a,b)*get2(p*2+1,mid+1,e,a,b))%MOD;
}

void filvec()
{
    vec.clear();
    int cnt=0;
    for(auto x:st){
        vec.push_back(-x);
        cnt++;
        if(cnt==L)break;
    }
    if(vec.empty()||vec.back()!=0)vec.push_back(0);
    reverse(vec.begin(),vec.end());
}

long long getansst()
{
    filvec();
    long long ret=0;
    long long sum2=1,val=0;
    for(int h=0;h<vec.size();h++){
        int i=vec[h];
        int i2;
        if(h==vec.size()-1)i2=n;
        else i2=vec[h+1];
        sum2*=x[i];
        long long cc=get(1,0,n-1,i,i2-1);
        long long u=sum2*cc;
        if((sum2>val)||(u>val)){
            sum2=1;
            ret=cc*get2(1,0,n-1,0,i);
            val=cc;
        }
    }
    ret%=MOD;
    return ret;
}

int init(int N, int X[], int Y[]){
    st.clear();
    n=N;
    for(int i=0;i<N;i++){
        x[i]=X[i];
        y[i]=Y[i];
        if(x[i]!=1){
            st.insert(-i);
        }
    }
    build(1,0,n-1);

    long long u=getansst();
    return u;
}

int updateX(int pos, int val) {

    if(x[pos]!=1)st.erase(-pos);
    x[pos]=val;
    if(x[pos]!=1)st.insert(-pos);

    update2(1,0,n-1,pos,val);

    long long u=getansst();
    return u;
}

int updateY(int pos, int val) {

    y[pos] = val;
    update(1,0,n-1,pos,val);

    long long u=getansst();
    return u;
}

Compilation message

horses.cpp: In function 'void filvec()':
horses.cpp:89:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   89 |     for(auto x:st){
      |              ^
horses.cpp:10:11: note: shadowed declaration is here
   10 | long long x[N];
      |           ^
horses.cpp: In function 'long long int getansst()':
horses.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int h=0;h<vec.size();h++){
      |                 ~^~~~~~~~~~~
horses.cpp:106:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         if(h==vec.size()-1)i2=n;
      |            ~^~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:121:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  121 | int init(int N, int X[], int Y[]){
      |          ~~~~^
horses.cpp:7:11: note: shadowed declaration is here
    7 | const int N=1e6+100;
      |           ^
horses.cpp:134:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |     return u;
      |            ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:146:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  146 |     return u;
      |            ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:155:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  155 |     return u;
      |            ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 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 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 240 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 7 ms 332 KB Output is correct
24 Correct 6 ms 340 KB Output is correct
25 Correct 7 ms 468 KB Output is correct
26 Correct 7 ms 468 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 7 ms 456 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 8 ms 460 KB Output is correct
31 Correct 3 ms 408 KB Output is correct
32 Correct 4 ms 328 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 54328 KB Output is correct
2 Correct 1415 ms 53452 KB Output is correct
3 Correct 1146 ms 56748 KB Output is correct
4 Correct 1328 ms 60520 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 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 1 ms 316 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 7 ms 340 KB Output is correct
24 Correct 7 ms 328 KB Output is correct
25 Correct 9 ms 468 KB Output is correct
26 Correct 7 ms 468 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 7 ms 340 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 7 ms 468 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 163 ms 30344 KB Output is correct
34 Correct 145 ms 30228 KB Output is correct
35 Correct 280 ms 52896 KB Output is correct
36 Correct 283 ms 52876 KB Output is correct
37 Correct 108 ms 30156 KB Output is correct
38 Correct 191 ms 42048 KB Output is correct
39 Correct 38 ms 29968 KB Output is correct
40 Correct 290 ms 53416 KB Output is correct
41 Correct 60 ms 30024 KB Output is correct
42 Correct 72 ms 30024 KB Output is correct
43 Correct 166 ms 53324 KB Output is correct
44 Correct 174 ms 53196 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 0 ms 316 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 0 ms 340 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 340 KB Output is correct
17 Correct 0 ms 316 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 8 ms 420 KB Output is correct
24 Correct 6 ms 340 KB Output is correct
25 Correct 6 ms 468 KB Output is correct
26 Correct 8 ms 476 KB Output is correct
27 Correct 6 ms 340 KB Output is correct
28 Correct 7 ms 460 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 7 ms 464 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 734 ms 52900 KB Output is correct
34 Correct 1325 ms 52880 KB Output is correct
35 Correct 1198 ms 56712 KB Output is correct
36 Correct 1268 ms 60592 KB Output is correct
37 Correct 167 ms 32608 KB Output is correct
38 Correct 152 ms 32536 KB Output is correct
39 Correct 287 ms 62908 KB Output is correct
40 Correct 312 ms 62808 KB Output is correct
41 Correct 110 ms 30796 KB Output is correct
42 Correct 208 ms 43568 KB Output is correct
43 Correct 37 ms 30504 KB Output is correct
44 Correct 268 ms 57972 KB Output is correct
45 Correct 62 ms 30540 KB Output is correct
46 Correct 73 ms 30608 KB Output is correct
47 Correct 207 ms 58356 KB Output is correct
48 Correct 198 ms 58316 KB Output is correct
49 Correct 1268 ms 35696 KB Output is correct
50 Correct 1095 ms 35764 KB Output is correct
51 Correct 1210 ms 64744 KB Output is correct
52 Correct 1294 ms 64292 KB Output is correct
53 Correct 731 ms 33868 KB Output is correct
54 Correct 1155 ms 47472 KB Output is correct
55 Correct 162 ms 31552 KB Output is correct
56 Correct 1363 ms 59804 KB Output is correct
57 Correct 374 ms 32184 KB Output is correct
58 Correct 510 ms 32640 KB Output is correct
59 Correct 200 ms 58348 KB Output is correct