oj.uz

답안 #849823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849823 2023-09-15T12:11:50 Z abcvuitunggio 말 (IOI15_horses) C++17
100 / 100
 588 ms 55964 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
set <pair <int, int>> s;
int n,st[2000001][2],x[500001],y[500001],mx[500001];
void build(int node, int l, int r){
    if (l==r){
        st[node][0]=x[l];
        st[node][1]=y[l];
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
    st[node][1]=max(st[node<<1][1],st[node<<1|1][1]);
}
void update(int node, int l, int r, int i, int val, int id){
    if (l>i||r<i)
        return;
    if (l==r){
        st[node][id]=val;
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i,val,id);
    update(node<<1|1,mid+1,r,i,val,id);
    st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
    st[node][1]=max(st[node<<1][1],st[node<<1|1][1]);
}
int getprod(int node, int l, int r, int u, int v){
    if (l>v||r<u||l>r||u>v)
        return 1;
    if (l>=u&&r<=v)
        return st[node][0];
    int mid=(l+r)>>1;
    return 1LL*getprod(node<<1,l,mid,u,v)*getprod(node<<1|1,mid+1,r,u,v)%mod;
}
int getmax(int node, int l, int r, int u, int v){
    if (l>v||r<u||l>r||u>v)
        return 1;
    if (l>=u&&r<=v)
        return st[node][1];
    int mid=(l+r)>>1;
    return max(getmax(node<<1,l,mid,u,v),getmax(node<<1|1,mid+1,r,u,v));
}
void add(int i){
    if (s.empty()){
        s.insert({0,st[1][1]});
        return;
    }
    auto it=s.upper_bound(make_pair(i,0));
    int val=getmax(1,0,n-1,i,(it==s.end()?n:(*it).first-1));
    mx[i]=val;
    if (it!=s.begin()){
        it--;
        auto p=*it;
        s.erase(it);
        p.second=getmax(1,0,n-1,p.first,i-1);
        mx[p.first]=p.second;
        s.insert(p);
    }
    s.insert({i,val});
}
void del(int i){
    if (!i)
        return;
    auto it=s.find({i,mx[i]});
    int r=n;
    if (it!=s.end()){
        it++;
        r=(*it).first-1;
        it--;
    }
    if (it!=s.begin()){
        it--;
        auto p=*it;
        s.erase(it);
        p.second=getmax(1,0,n-1,p.first,r);
        mx[p.first]=p.second;
        s.insert(p);
    }
    s.erase({i,mx[i]});
}
int calc(){
    auto it=--s.end();
    for (int i=0;i<31;i++){
        if (it==s.begin())
            break;
        it--;
    }
    auto res=*it;
    int cur=1;
    it++;
    while (it!=s.end()){
        auto p=*it;
        if (x[p.first]>res.second/cur){
            res=p;
            cur=1;
            it++;
            continue;
        }
        cur*=x[p.first];
        if (p.second>res.second/cur){
            res=p;
            cur=1;
            it++;
            continue;
        }
        it++;
    }
    return 1LL*getprod(1,0,n-1,0,res.first)*res.second%mod;
}
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];
    }
    build(1,0,n-1);
    for (int i=0;i<n;i++)
        if (!i||x[i]>1)
            add(i);
    return calc();
}
int updateX(int pos, int val){
    update(1,0,n-1,pos,val,0);
    if (x[pos]==1&&val>1)
        add(pos);
    if (x[pos]>1&&val==1)
        del(pos);
    x[pos]=val;
    return calc();
}
int updateY(int pos, int val){
    y[pos]=val;
    update(1,0,n-1,pos,val,1);
    auto it=s.upper_bound({pos,1000000001});
    it--;
    int p=(*it).first;
    s.erase(it);
    add(p);
	return calc();
}

Compilation message

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:16:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |     st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void update(int, int, int, int, int, int)':
horses.cpp:29:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |     st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int getprod(int, int, int, int, int)':
horses.cpp:38:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   38 |     return 1LL*getprod(node<<1,l,mid,u,v)*getprod(node<<1|1,mid+1,r,u,v)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int calc()':
horses.cpp:113:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |     return 1LL*getprod(1,0,n-1,0,res.first)*res.second%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6488 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 2 ms 6488 KB Output is correct
24 Correct 2 ms 6500 KB Output is correct
25 Correct 3 ms 6488 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 2 ms 6488 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 1 ms 6488 KB Output is correct
30 Correct 2 ms 6488 KB Output is correct
31 Correct 2 ms 6488 KB Output is correct
32 Correct 2 ms 6488 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 43116 KB Output is correct
2 Correct 562 ms 55844 KB Output is correct
3 Correct 514 ms 47136 KB Output is correct
4 Correct 461 ms 51144 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6688 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6488 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 2 ms 6488 KB Output is correct
24 Correct 2 ms 6488 KB Output is correct
25 Correct 2 ms 6488 KB Output is correct
26 Correct 2 ms 6488 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 2 ms 6488 KB Output is correct
29 Correct 1 ms 6488 KB Output is correct
30 Correct 2 ms 6744 KB Output is correct
31 Correct 2 ms 6492 KB Output is correct
32 Correct 2 ms 6488 KB Output is correct
33 Correct 41 ms 19024 KB Output is correct
34 Correct 38 ms 19032 KB Output is correct
35 Correct 375 ms 42292 KB Output is correct
36 Correct 366 ms 42400 KB Output is correct
37 Correct 26 ms 18776 KB Output is correct
38 Correct 190 ms 30896 KB Output is correct
39 Correct 20 ms 18520 KB Output is correct
40 Correct 365 ms 42420 KB Output is correct
41 Correct 25 ms 18780 KB Output is correct
42 Correct 36 ms 18776 KB Output is correct
43 Correct 335 ms 42320 KB Output is correct
44 Correct 341 ms 42216 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6736 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6488 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 3 ms 6492 KB Output is correct
26 Correct 2 ms 6672 KB Output is correct
27 Correct 2 ms 6496 KB Output is correct
28 Correct 2 ms 6500 KB Output is correct
29 Correct 1 ms 6504 KB Output is correct
30 Correct 2 ms 6492 KB Output is correct
31 Correct 2 ms 6492 KB Output is correct
32 Correct 3 ms 6492 KB Output is correct
33 Correct 514 ms 43296 KB Output is correct
34 Correct 588 ms 55964 KB Output is correct
35 Correct 579 ms 46932 KB Output is correct
36 Correct 463 ms 50964 KB Output is correct
37 Correct 52 ms 22864 KB Output is correct
38 Correct 39 ms 22868 KB Output is correct
39 Correct 376 ms 53324 KB Output is correct
40 Correct 381 ms 53172 KB Output is correct
41 Correct 26 ms 20820 KB Output is correct
42 Correct 188 ms 33876 KB Output is correct
43 Correct 21 ms 20624 KB Output is correct
44 Correct 369 ms 48192 KB Output is correct
45 Correct 24 ms 20816 KB Output is correct
46 Correct 27 ms 20816 KB Output is correct
47 Correct 347 ms 48728 KB Output is correct
48 Correct 352 ms 48708 KB Output is correct
49 Correct 217 ms 26040 KB Output is correct
50 Correct 192 ms 26004 KB Output is correct
51 Correct 549 ms 55212 KB Output is correct
52 Correct 474 ms 54608 KB Output is correct
53 Correct 134 ms 24108 KB Output is correct
54 Correct 299 ms 37892 KB Output is correct
55 Correct 75 ms 21780 KB Output is correct
56 Correct 467 ms 50028 KB Output is correct
57 Correct 103 ms 22268 KB Output is correct
58 Correct 135 ms 22880 KB Output is correct
59 Correct 357 ms 48756 KB Output is correct