oj.uz

Submission #849812

# Submission time Handle Problem Language Result Execution time Memory
849812 2023-09-15T12:02:06 Z abcvuitunggio Horses (IOI15_horses) C++17
0 / 100
 512 ms 43612 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(){
    //for (auto [i,j]:s)
      //  cout << i << ' ' << j << '\n';
    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.first/cur){
            res=p;
            cur=1;
            it++;
            continue;
        }
        cur*=x[p.first];
        if (p.second>res.first/cur){
            res=p;
            cur=1;
            it++;
            continue;
        }
        cur*=p.second;
        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:116:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |     return 1LL*getprod(1,0,n-1,0,res.first)*res.second%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Incorrect 1 ms 6488 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6744 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 6596 KB Output is correct
9 Incorrect 1 ms 6488 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6684 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 6588 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 Incorrect 1 ms 6488 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6744 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 6488 KB Output is correct
9 Incorrect 1 ms 6488 KB Output isn't correct
10 Halted 0 ms 0 KB -