oj.uz

Submission #998899

# Submission time Handle Problem Language Result Execution time Memory
998899 2024-06-14T20:30:28 Z inesfi Horses (IOI15_horses) C++14
17 / 100
 303 ms 65364 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

const ll MODULO=1000*1000*1000+7,PUISS=1048576;
ll arbreprixmaxi[PUISS+1],arbremultiprod[PUISS+1];
ll nbannees,decalage,nb1,ancien,deb,fin,atester,zero,dernier,debec,finec,produit;
set<pair<ll,ll>> inter;
set<pair<ll,ll>>::iterator it;

ll maxi(ll a,ll b){
    if (a==b){
        return arbreprixmaxi[a];
    }
    if (a%2==1){
        return max(arbreprixmaxi[a],maxi(a+1,b));
    }
    if (b%2==0){
        return max(arbreprixmaxi[b],maxi(a,b-1));
    }
    return maxi(a/2,b/2);
}

ll prod(ll a,ll b){
    if (a==b){
        return arbremultiprod[a];
    }
    if (a%2==1){
        return (arbremultiprod[a]*prod(a+1,b))%MODULO;
    }
    if (b%2==0){
        return (arbremultiprod[b]*prod(a,b-1))%MODULO;
    }
    return prod(a/2,b/2);
}

void remonteprix(ll endroit){
    if (endroit==0){
        return ;
    }
    arbreprixmaxi[endroit]=max(arbreprixmaxi[2*endroit],arbreprixmaxi[2*endroit+1]);
    remonteprix(endroit/2);
}

void remontemulti(ll endroit){
    if (endroit==0){
        return ;
    }
    arbremultiprod[endroit]=(arbreprixmaxi[2*endroit]*arbreprixmaxi[2*endroit+1])%MODULO;
    remontemulti(endroit/2);
}

ll trouver(){
    zero=0;
    atester=max((ll)inter.size()-62,zero);
    dernier=atester+1;
    produit=1;
    it=inter.end();
    for (int i=inter.size();i>atester;i--){
        it--;
    }
    deb=(*(it)).first;
    fin=(*(it)).second;
    it++;
    while (dernier<(int)inter.size()){
        debec=(*(it)).first;
        finec=(*(it)).second;
        if (maxi(deb+decalage,fin+decalage)>=maxi(debec+decalage,finec+decalage)*produit 
		and maxi(deb+decalage,fin+decalage)>=maxi(debec+decalage,finec+decalage)*produit*arbremultiprod[debec+decalage]){
            produit*=arbremultiprod[debec+decalage];
        }
        else {
            atester=dernier;
            deb=debec;
            fin=finec;
            produit=1;
        }
        it++;
		dernier++;
    }
    //cout<<maxi(deb+decalage,fin+decalage)<<" "<<prod(decalage,fin+decalage)<<endl;
    return (maxi(deb+decalage,fin+decalage)*prod(decalage,fin+decalage))%MODULO;
}

int init (int N, int X[], int Y[]){
	nbannees=N;
    decalage=PUISS/2;
    for (int i=0;i<PUISS/2;i++){
        arbremultiprod[i+decalage]=1;
    }
    for (int iannee=0;iannee<nbannees;iannee++){
        arbreprixmaxi[iannee+decalage]=Y[iannee];
        arbremultiprod[iannee+decalage]=X[iannee];
    }
    for (int icase=decalage-1;icase>=0;icase--){
        arbreprixmaxi[icase]=max(arbreprixmaxi[2*icase],arbreprixmaxi[2*icase+1]);
        arbremultiprod[icase]=(arbremultiprod[2*icase]*arbremultiprod[2*icase+1])%MODULO;
    }
    for (int icase=0;icase<nbannees;icase++){
        if (X[icase]!=1){
            if (nb1>0){
                inter.insert(make_pair(icase-nb1,icase-1));
            }
            inter.insert(make_pair(icase,icase));
            nb1=0;
        }
        else {
            nb1++;
        }
    }
    if (nb1>0){
        inter.insert(make_pair(nbannees-nb1,nbannees-1));
    }
    return trouver();
}

int updateX(int pos, int val){
    ancien=arbremultiprod[pos+decalage];
    arbremultiprod[pos+decalage]=val;
    remontemulti((pos+decalage)/2);
    it=inter.lower_bound(make_pair(pos,0));
    if (it==inter.end() or (*(it)).first>pos){
        it--;
    }
    deb=(*(it)).first;
    fin=(*(it)).second;
    if (val!=1){
        if (ancien==1){
            if (deb==pos){
                if (fin!=pos){
                    inter.insert(make_pair(pos,pos));
                    inter.insert(make_pair(pos+1,fin));
                    inter.erase(it);
                }
            }
            else {
                if (fin==pos){
                    inter.insert(make_pair(pos,pos));
                    inter.insert(make_pair(deb,pos-1));
                    inter.erase(it);
                }
                else {
                    inter.insert(make_pair(pos,pos));
                    inter.insert(make_pair(deb,pos-1));
                    inter.insert(make_pair(pos+1,fin));
                }
            }
        }
    }
    else {
        if (ancien!=1){
            if (pos==0){
                if (arbremultiprod[decalage+1]==1){
                    it=inter.erase(it);
                    inter.insert(make_pair(pos,(*(it)).second));
                    inter.erase(it);
                }
            }
            else {
                if (arbremultiprod[decalage+pos-1]==1){
                    it=inter.erase(it);
                    it--;
                    inter.insert(make_pair((*(it)).first,pos));
                    it=inter.erase(it);
                }
                if (arbremultiprod[decalage+pos+1]==1){
                    deb=(*(it)).first;
                    it=inter.erase(it);
                    it++;
                    inter.insert(make_pair(deb,(*(it)).second));
                    inter.erase(it);
                }
            }
        }
    }
    return trouver();
}

int updateY(int pos, int val){
    arbreprixmaxi[pos+decalage]=val;
    remonteprix((pos+decalage)/2);
    return trouver();
}

Compilation message

horses.cpp: In function 'long long int trouver()':
horses.cpp:61:26: warning: conversion from 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   61 |     for (int i=inter.size();i>atester;i--){
      |                ~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |     for (int icase=decalage-1;icase>=0;icase--){
      |                    ~~~~~~~~^~
horses.cpp:116:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |     return trouver();
      |            ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:178:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  178 |     return trouver();
      |            ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:184:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  184 |     return trouver();
      |            ~~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12736 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12744 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12736 KB Output is correct
13 Correct 3 ms 12732 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12764 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12760 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12756 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12744 KB Output is correct
15 Correct 3 ms 12756 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12888 KB Output is correct
19 Correct 3 ms 12732 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Runtime error 11 ms 25804 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 56644 KB Output is correct
2 Incorrect 303 ms 65364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12940 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12732 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12736 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12736 KB Output is correct
15 Correct 3 ms 12888 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Runtime error 13 ms 26040 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12768 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 13144 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12764 KB Output is correct
18 Correct 3 ms 12888 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 2 ms 12892 KB Output is correct
21 Runtime error 11 ms 25808 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -