oj.uz

Submission #199729

# Submission time Handle Problem Language Result Execution time Memory
199729 2020-02-03T02:06:16 Z FieryPhoenix Horses (IOI15_horses) C++11
100 / 100
 452 ms 64888 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include <horses.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
 
int N;
ll worth[1005],X[500001],Y[500001];
bool over[1005];
set<int>bigInd;
ll treeMax[1000001],treeMult[1000001];
 
void updateMax(int pos, int val){
  pos+=N;
  treeMax[pos]=val;
  for (pos/=2;pos>=1;pos/=2)
    treeMax[pos]=max(treeMax[pos*2],treeMax[pos*2+1]);
}
 
ll queryMax(int L, int R){
  L+=N; R+=N;
  ll ans=0;
  while (L<=R){
    if (L%2==1)
      ans=max(ans,treeMax[L++]);
    if (R%2==0)
      ans=max(ans,treeMax[R--]);
    L/=2;
    R/=2;
  }
  return ans;
}
 
void updateMult(int pos, int val){
  pos+=N;
  treeMult[pos]=val;
  for (pos/=2;pos>=1;pos/=2)
    treeMult[pos]=(treeMult[pos*2]*treeMult[pos*2+1])%MOD;
}
 
int queryMult(int L, int R){
  L+=N; R+=N;
  ll ans=1;
  while (L<=R){
    if (L%2==1)
      ans*=treeMult[L++];
    ans%=MOD;
    if (R%2==0)
      ans*=treeMult[R--];
    ans%=MOD;
    L/=2;
    R/=2;
  }
  return ans;
}
 
int calc(){
  if (bigInd.size()==0)
    return queryMax(0,N-1);
  vector<int>v;
  set<int>::iterator it=bigInd.end();
  it--;
  for (;;){
    v.push_back(*it);
    if (it==bigInd.begin() || v.size()==31)
      break;
    it--;
  }
  reverse(v.begin(),v.end());
  int M=v.size();
  for (int i=0;i<=M;i++){
    worth[i]=0;
    over[i]=false;
  }
  for (int i=M-1;i>=0;i--){
    if (over[i+1])
      worth[i]=X[v[i]]*worth[i+1];
    else{
      int L=v[i];
      int R;
      if (i==M-1)
	R=N-1;
      else
	R=v[i+1]-1;
      assert(L<=R);
      worth[i]=X[v[i]]*max(queryMax(L,R),worth[i+1]);
    }
    over[i]=(worth[i]>1000000000) | over[i+1];
    if (over[i])
      worth[i]%=MOD;
  }
  if (!over[0])
    return max(worth[0],queryMax(0,v[0]-1));
  return (worth[0]*queryMult(0,v[0]-1))%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];
    updateMax(i,Y[i]);
    updateMult(i,X[i]);
    if (X[i]>1)
      bigInd.insert(i);
  }
  return calc();
}
 
int updateX(int pos, int val){
  if (X[pos]>1 && val==1)
    bigInd.erase(pos);
  else if (X[pos]==1 && val>1)
    bigInd.insert(pos);
  X[pos]=val;
  updateMult(pos,val);
  return calc();
}
 
int updateY(int pos, int val){
  Y[pos]=val;
  updateMax(pos,val);
  return calc();
}

Compilation message

horses.cpp: In function 'int queryMult(int, int)':
horses.cpp:79:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return ans;
          ^~~
horses.cpp: In function 'int calc()':
horses.cpp:84:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return queryMax(0,N-1);
            ~~~~~~~~^~~~~~~
horses.cpp:95:15: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   int M=v.size();
         ~~~~~~^~
horses.cpp:118:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return max(worth[0],queryMax(0,v[0]-1));
            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:119:40: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return (worth[0]*queryMult(0,v[0]-1))%MOD;
                                        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:127:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateMax(i,Y[i]);
                 ~~~^
horses.cpp:128:21: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateMult(i,X[i]);
                  ~~~^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 380 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 7 ms 376 KB Output is correct
24 Correct 7 ms 504 KB Output is correct
25 Correct 7 ms 504 KB Output is correct
26 Correct 7 ms 504 KB Output is correct
27 Correct 6 ms 376 KB Output is correct
28 Correct 7 ms 504 KB Output is correct
29 Correct 6 ms 376 KB Output is correct
30 Correct 7 ms 504 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 7 ms 376 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 52332 KB Output is correct
2 Correct 431 ms 52344 KB Output is correct
3 Correct 401 ms 52344 KB Output is correct
4 Correct 411 ms 52344 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 372 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 6 ms 376 KB Output is correct
24 Correct 6 ms 504 KB Output is correct
25 Correct 7 ms 504 KB Output is correct
26 Correct 7 ms 504 KB Output is correct
27 Correct 7 ms 504 KB Output is correct
28 Correct 7 ms 504 KB Output is correct
29 Correct 6 ms 376 KB Output is correct
30 Correct 6 ms 508 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 7 ms 376 KB Output is correct
33 Correct 143 ms 27896 KB Output is correct
34 Correct 151 ms 31864 KB Output is correct
35 Correct 295 ms 62176 KB Output is correct
36 Correct 301 ms 62200 KB Output is correct
37 Correct 139 ms 30072 KB Output is correct
38 Correct 201 ms 42936 KB Output is correct
39 Correct 125 ms 29816 KB Output is correct
40 Correct 288 ms 57208 KB Output is correct
41 Correct 132 ms 29944 KB Output is correct
42 Correct 131 ms 29944 KB Output is correct
43 Correct 261 ms 57736 KB Output is correct
44 Correct 262 ms 57604 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 7 ms 376 KB Output is correct
24 Correct 7 ms 376 KB Output is correct
25 Correct 6 ms 504 KB Output is correct
26 Correct 7 ms 504 KB Output is correct
27 Correct 6 ms 376 KB Output is correct
28 Correct 6 ms 504 KB Output is correct
29 Correct 6 ms 376 KB Output is correct
30 Correct 7 ms 504 KB Output is correct
31 Correct 7 ms 376 KB Output is correct
32 Correct 7 ms 504 KB Output is correct
33 Correct 363 ms 53880 KB Output is correct
34 Correct 449 ms 64888 KB Output is correct
35 Correct 402 ms 56056 KB Output is correct
36 Correct 433 ms 59896 KB Output is correct
37 Correct 143 ms 31992 KB Output is correct
38 Correct 145 ms 31864 KB Output is correct
39 Correct 300 ms 62328 KB Output is correct
40 Correct 299 ms 62200 KB Output is correct
41 Correct 142 ms 30072 KB Output is correct
42 Correct 194 ms 42840 KB Output is correct
43 Correct 126 ms 29816 KB Output is correct
44 Correct 277 ms 57336 KB Output is correct
45 Correct 128 ms 29944 KB Output is correct
46 Correct 128 ms 30072 KB Output is correct
47 Correct 262 ms 57720 KB Output is correct
48 Correct 262 ms 57568 KB Output is correct
49 Correct 305 ms 34936 KB Output is correct
50 Correct 302 ms 34936 KB Output is correct
51 Correct 452 ms 64248 KB Output is correct
52 Correct 435 ms 63736 KB Output is correct
53 Correct 311 ms 33144 KB Output is correct
54 Correct 339 ms 46840 KB Output is correct
55 Correct 187 ms 31096 KB Output is correct
56 Correct 426 ms 59132 KB Output is correct
57 Correct 206 ms 31584 KB Output is correct
58 Correct 241 ms 31992 KB Output is correct
59 Correct 263 ms 57720 KB Output is correct