Submission #483951

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
483951	2021-11-01 14:29:41	Cross_Ratio	Horses (IOI15_horses)	C++14	100 / 100	477 ms	34216 KiB

horses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int p = 1e9 + 7;
typedef pair<int,int> P;
struct SegTree {
    vector<int> seg1, seg2, seg3;
    int MAX;
    void init(int N) {
        int i;
        for(i=2;i<2*N;i*=2) {}
        MAX = i;
        seg1.resize(i);
        seg2.resize(i);
        seg3.resize(i);
    }
    void cons() {
        for(int i=MAX/2-1;i>=1;i--) {
            seg1[i] = max(seg1[2*i],seg1[2*i+1]);
            seg2[i] = max(seg2[2*i],seg2[2*i+1]);
            seg3[i] = 1LL * seg3[2*i] * seg3[2*i+1] % p;
        }
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg1[n] = max(seg1[2*n],seg1[2*n+1]);
            seg2[n] = max(seg2[2*n],seg2[2*n+1]);
            seg3[n] = 1LL * seg3[2*n] * seg3[2*n+1] % p;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

horses.cpp: In member function 'void SegTree::cons()':
horses.cpp:21:53: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   21 |             seg3[i] = 1LL * seg3[2*i] * seg3[2*i+1] % p;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In member function 'void SegTree::update(int)':
horses.cpp:30:53: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   30 |             seg3[n] = 1LL * seg3[2*n] * seg3[2*n+1] % p;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In member function 'int SegTree::sum1(int, int, int, int, int)':
horses.cpp:37:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
horses.cpp: In member function 'int SegTree::sum2(int, int, int, int, int)':
horses.cpp:43:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
horses.cpp: In member function 'int SegTree::sum3(int, int, int, int, int)':
horses.cpp:49:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
horses.cpp:50:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |         return 1LL * sum3(s,e,2*n,ns,mid)*sum3(s,e,2*n+1,mid,ne) % p;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:121:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  121 |     while(pt >= 0 && cnt <= 1e9) {
      |                      ^~~
horses.cpp:128:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |             ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:134:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |             ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:108:12: warning: unused variable 'j' [-Wunused-variable]
  108 |     int i, j;
      |            ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:148:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  148 |     while(pt >= 0 && cnt <= 1e9) {
      |                      ^~~
horses.cpp:154:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  154 |             ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:160:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |             ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:174:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  174 |     while(pt >= 0 && cnt <= 1e9) {
      |                      ^~~
horses.cpp:180:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  180 |             ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:186:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  186 |             ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23