oj.uz

Submission #856957

# Submission time Handle Problem Language Result Execution time Memory
856957 2023-10-05T01:37:29 Z onepunchac168 Horses (IOI15_horses) C++14
17 / 100
 180 ms 115832 KB 
//------------------------------------\\
//   ------------------------------   \\
//  |  created by Dinh Manh Hung   |  \\
//  |      tht.onepunchac168       |  \\
//  |     THPT CHUYEN HA TINH      |  \\
//  |      HA TINH, VIET NAM       |  \\
//  |           Siuuu              |  \\
//   ------------------------------   \\
//------------------------------------\\

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define            task     ""
#define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define             ldb     long double
#define              pb     push_back
#define              eb     emplace_back
#define              fi     first
#define              se     second
#define           all(x)    begin(x),end(x)
#define       uniquev(v)    v.resize(unique(all(v))-v.begin())
#define       rep(i,a,b)    for (int i=a;i<=b;i++)
#define        cntbit(v)    __builtin_popcountll(v)
#define         gcd(a,b)    __gcd(a,b)
#define         lcm(a,b)    ((1LL*a*b)/__gcd(a,b))
#define          mask(x)    (1LL<<(x))
#define     readbit(x,i)    ((x>>i)&1)
#define             Yes     cout << "Yes"
#define             YES     cout << "YES"
#define              No     cout << "No"
#define              NO     cout << "NO"

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const ll mod=1e9+7;
const char nl = '\n';

inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = (xo<<1) + (xo<<3) + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}

// DEBUG
/*
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
*/

/* END OF TEMPLATE*/

// ================= Solution =================//

/*
void onepunchac168();

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    file(task);
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--)
    {
        onepunchac168();
    }
}

const int N=2e5+5;

void onepunchac168()
{

}
// goodbye see ya
*/
const int N=5e5+5;
int n;
int x[N];
int y[N];
struct Node{
    ii val;
    ii pref;
    ii suff;
    Node()
    {

    }
} T[4*N];
const ll inf=1e9;
Node merge(Node &a,Node &b)
{
    Node target;
    bool check=false;
    if (a.suff.se==-1||b.pref.se==-1)
    {
        check=true;
    }
    else if (a.suff.fi*b.pref.fi>y[a.val.se])
    {
        check=true;
    }
    else if (a.suff.fi*b.pref.fi*x[b.val.se]>y[a.val.se])
    {
        check=true;
    }
    else if (a.suff.fi*b.pref.fi*x[b.val.se]*y[b.val.se]>y[a.val.se])
    {
        check=true;
    }
    if (check==true)
    {
        bool cka=true;
        target.suff=b.suff;
        if (a.pref.se==-1||b.pref.se==-1||a.suff.se==-1)
        {
            cka=false;
        }
        else
        {
            ll aa=a.pref.fi*x[a.val.se];
            if (aa>inf)
            {
                cka=false;
            }
            else
            {
                aa=aa*b.pref.fi;
                if (aa>inf)
                {
                    cka=false;
                }
                else
                {
                    aa=aa*a.suff.fi;
                    if (aa>inf)
                    {
                        cka=false;
                    }
                }
            }
        }
        if (cka==false)
        {
            target.pref.se=-1;
            target.pref.fi=(((a.pref.fi*x[a.val.se])%mod)*((b.pref.fi*a.suff.fi)%mod))%mod;
        }
        else
        {
            target.pref.se=0;
            target.pref.fi=(((a.pref.fi*x[a.val.se])%mod)*((b.pref.fi*a.suff.fi)%mod))%mod;
        }
        target.val=b.val;
        target.val.fi=(((target.val.fi*a.pref.fi)%mod)*((x[a.val.se]*a.suff.fi)%mod))%mod;
        return target;
    }
    target.val=a.val;
    target.pref=a.pref;
    bool cp=true;
    if (a.suff.se==-1||b.pref.se==-1||b.suff.se==-1)
    {
        cp=false;
    }
    else
    {
        ll aa=a.suff.fi;
        aa=aa*b.pref.fi;
        if (aa>inf)
        {
            cp=false;
        }
        else
        {
            aa=aa*x[b.val.se];
            if (aa>inf)
            {
                cp=false;
            }
            else
            {
                aa=aa*b.suff.fi;
                if (aa>inf)
                {
                    cp=false;
                }
            }
        }
    }
    if (cp==false)
    {
        target.suff.se=-1;
        target.suff.fi=(((a.suff.fi*b.pref.fi)%mod)*((b.suff.fi*x[b.val.se])%mod))%mod;
    }
    else
    {
        target.suff.se=0;
        target.suff.fi=(((a.suff.fi*b.pref.fi)%mod)*((b.suff.fi*x[b.val.se])%mod))%mod;
    }
    return target;
}
void build(int node,int l,int r)
{
    if (l==r)
    {
        T[node].val={(x[l]*y[l])%mod,l};
        T[node].pref={1,0};
        T[node].suff={1,0};
        return;
    }
    build(node*2,l,(l+r)/2);
    build(node*2+1,(l+r)/2+1,r);
    T[node]=merge(T[node*2],T[node*2+1]);
}
void update(int node,int l,int r,int u)
{
    if (l>u||r<u)
    {
        return;
    }
    if (l==r)
    {
        T[node].val={(x[l]*y[l])%mod,l};
        T[node].pref={1,0};
        T[node].suff={1,0};
        return;
    }
    update(node*2,l,(l+r)/2,u);
    update(node*2+1,(l+r)/2+1,r,u);
    T[node]=merge(T[node*2],T[node*2+1]);
}

int init(int Na, int Xa[], int Ya[]) {
    n=Na;
    for (int i=1;i<=n;i++)
    {
        x[i]=Xa[i-1];
        y[i]=Ya[i-1];
    }
    build(1,1,n);
    return T[1].val.fi;
}

int updateX(int pos, int val) {
    pos++;
	x[pos]=val;
	update(1,1,n,pos);
	return T[1].val.fi;
}

int updateY(int pos, int val) {
    pos++;
	y[pos]=val;
	update(1,1,n,pos);
	return T[1].val.fi;
}

Compilation message

horses.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\\
      | ^
horses.cpp: In function 'int ReadInt()':
horses.cpp:52:22: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   52 |     for (co = getchar(); co < '0' || co > '9'; co = getchar());
      |               ~~~~~~~^~
horses.cpp:52:60: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   52 |     for (co = getchar(); co < '0' || co > '9'; co = getchar());
      |                                                     ~~~~~~~^~
horses.cpp:54:22: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   54 |     for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
      |               ~~~~~~~^~
horses.cpp:54:62: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   54 |     for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
      |                                                       ~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:20:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 | #define              fi     first
      |                             ^
horses.cpp:290:21: note: in expansion of macro 'fi'
  290 |     return T[1].val.fi;
      |                     ^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:20:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 | #define              fi     first
      |                             ^
horses.cpp:297:18: note: in expansion of macro 'fi'
  297 |  return T[1].val.fi;
      |                  ^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:20:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 | #define              fi     first
      |                             ^
horses.cpp:304:18: note: in expansion of macro 'fi'
  304 |  return T[1].val.fi;
      |                  ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96856 KB Output is correct
2 Correct 13 ms 97004 KB Output is correct
3 Correct 13 ms 96860 KB Output is correct
4 Correct 13 ms 96860 KB Output is correct
5 Correct 13 ms 96860 KB Output is correct
6 Correct 13 ms 96860 KB Output is correct
7 Correct 14 ms 96860 KB Output is correct
8 Correct 13 ms 97068 KB Output is correct
9 Correct 13 ms 96904 KB Output is correct
10 Correct 13 ms 96860 KB Output is correct
11 Correct 13 ms 96900 KB Output is correct
12 Correct 14 ms 96856 KB Output is correct
13 Correct 14 ms 96948 KB Output is correct
14 Correct 13 ms 96860 KB Output is correct
15 Correct 13 ms 96924 KB Output is correct
16 Correct 13 ms 96860 KB Output is correct
17 Correct 13 ms 96940 KB Output is correct
18 Correct 13 ms 96860 KB Output is correct
19 Correct 13 ms 96856 KB Output is correct
20 Correct 13 ms 96860 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 96860 KB Output is correct
2 Correct 13 ms 96860 KB Output is correct
3 Correct 13 ms 96856 KB Output is correct
4 Correct 13 ms 96856 KB Output is correct
5 Correct 13 ms 96900 KB Output is correct
6 Correct 13 ms 97004 KB Output is correct
7 Correct 15 ms 96860 KB Output is correct
8 Correct 14 ms 97064 KB Output is correct
9 Correct 13 ms 96856 KB Output is correct
10 Correct 14 ms 96860 KB Output is correct
11 Correct 13 ms 97040 KB Output is correct
12 Correct 13 ms 96860 KB Output is correct
13 Correct 14 ms 96860 KB Output is correct
14 Correct 13 ms 96856 KB Output is correct
15 Correct 13 ms 97024 KB Output is correct
16 Correct 13 ms 96860 KB Output is correct
17 Correct 14 ms 96808 KB Output is correct
18 Correct 13 ms 96856 KB Output is correct
19 Correct 15 ms 97268 KB Output is correct
20 Correct 14 ms 96920 KB Output is correct
21 Incorrect 13 ms 96856 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 102996 KB Output is correct
2 Incorrect 180 ms 115832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97000 KB Output is correct
2 Correct 15 ms 96852 KB Output is correct
3 Correct 13 ms 96860 KB Output is correct
4 Correct 13 ms 96872 KB Output is correct
5 Correct 13 ms 96856 KB Output is correct
6 Correct 16 ms 96856 KB Output is correct
7 Correct 13 ms 96856 KB Output is correct
8 Correct 13 ms 96860 KB Output is correct
9 Correct 13 ms 97044 KB Output is correct
10 Correct 14 ms 97020 KB Output is correct
11 Correct 13 ms 96860 KB Output is correct
12 Correct 14 ms 96860 KB Output is correct
13 Correct 15 ms 96928 KB Output is correct
14 Correct 14 ms 97032 KB Output is correct
15 Correct 13 ms 96856 KB Output is correct
16 Correct 14 ms 96860 KB Output is correct
17 Correct 13 ms 96944 KB Output is correct
18 Correct 13 ms 96856 KB Output is correct
19 Correct 13 ms 97016 KB Output is correct
20 Correct 13 ms 96860 KB Output is correct
21 Incorrect 13 ms 97064 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97004 KB Output is correct
2 Correct 14 ms 97020 KB Output is correct
3 Correct 13 ms 96856 KB Output is correct
4 Correct 13 ms 96940 KB Output is correct
5 Correct 14 ms 96860 KB Output is correct
6 Correct 13 ms 96860 KB Output is correct
7 Correct 14 ms 96908 KB Output is correct
8 Correct 13 ms 96860 KB Output is correct
9 Correct 14 ms 96872 KB Output is correct
10 Correct 14 ms 96860 KB Output is correct
11 Correct 15 ms 96940 KB Output is correct
12 Correct 13 ms 96860 KB Output is correct
13 Correct 13 ms 96944 KB Output is correct
14 Correct 14 ms 96860 KB Output is correct
15 Correct 14 ms 96856 KB Output is correct
16 Correct 15 ms 96860 KB Output is correct
17 Correct 13 ms 96860 KB Output is correct
18 Correct 13 ms 96992 KB Output is correct
19 Correct 13 ms 96860 KB Output is correct
20 Correct 14 ms 96860 KB Output is correct
21 Incorrect 13 ms 96860 KB Output isn't correct
22 Halted 0 ms 0 KB -