Submission #483939

#	Time	Username	Problem	Language	Result	Execution time	Memory
483939		Cross_Ratio	Horses (IOI15_horses)	C++14	57 / 100	1596 ms	31544 KiB

horses

#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;
            n /= 2;
        }
    }
    int sum1(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg1[n];
        int mid = ns + ne >> 1;
        return max(sum1(s,e,2*n,ns,mid),sum1(s,e,2*n+1,mid,ne));
    }
    int sum2(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg2[n];
        int mid = ns + ne >> 1;
        return max(sum2(s,e,2*n,ns,mid),sum2(s,e,2*n+1,mid,ne));
    }
    int sum3(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 1;
        if(s<=ns&&ne<=e) return seg3[n];
        int mid = ns + ne >> 1;
        return 1LL * sum3(s,e,2*n,ns,mid)*sum3(s,e,2*n+1,mid,ne) % p;
    }
    int sum1(int s, int e) {
        if(s >= e) return 0;
        return sum1(s, e, 1, 0, MAX/2);
    }
    int sum2(int s, int e) {
        if(s >= e) return 0;
        return sum2(s, e, 1, 0, MAX/2);
    }
    int sum3(int s, int e) {
        if(s >= e) return 1;
        return sum3(s, e, 1, 0, MAX/2);
    }
    void Edit(int t, int n, int a) {
        if(t == 1) {
            seg1[n+MAX/2] = a;
            seg3[n+MAX/2] = a;
        }
        if(t == 2) seg2[n+MAX/2] = a;
        update(n);
    }
    P get_left(int k) {
        int s = 0, e = k+1;
        while(s + 1 < e) {
            int mid = s + e >> 1;
            if(sum1(mid,k)==1) {
                if(seg1[mid-1+MAX/2] >= 2) {
                    s = mid;
                    break;
                }
                else e = mid;
            }
            else s = mid;
        }
        return P(s,sum2(s,k));
    }
};
SegTree tree;
int N;
vector<int> X, Y;
int init(int N2, int X2[], int Y2[]) {
    N = N2;
    for(int i = 0; i < N;i++) {
      X.push_back(X2[i]);
      Y.push_back(Y2[i]);
    }
    tree.init(N+5);
    //cout << "st\n";
    int MAX = tree.MAX;
    int i, j;
    for(i=0;i<N;i++) {
        tree.seg1[i+MAX/2] = X[i];
        tree.seg2[i+MAX/2] = Y[i];
        tree.seg3[i+MAX/2] = X[i];
    }
    tree.cons();
    //cout <<"st2\n";
    long long int cnt = 1;
    int pt = N;
    long long int macnt = 1;
    int ma = 0;
    int ans = 0;
    while(pt >= 0 && cnt <= 1e9) {
        P k = tree.get_left(pt);
        //cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
        pt = k.first - 1;
        if(macnt * k.second > cnt * ma) {
            //cout << "E1\n";
            macnt = cnt;
            ma = k.second;
            ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
        }
        if(pt < 0) break;
        if(macnt * Y[pt] > cnt * ma) {
            //cout << "E2\n";
            macnt = cnt;
            ma = Y[pt];
            ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
        }
        cnt *= X[pt];
        //cout <<pt << ' ' << ans << '\n';
    }
    return ans;
}
int updateX(int pos, int val) {
    tree.Edit(1,pos,val);
  	X[pos] = val;
    long long int cnt = 1;
    int pt = N;
    long long int macnt = 1;
    int ma = 0;
    int ans = 0;
    while(pt >= 0 && cnt <= 1e9) {
        P k = tree.get_left(pt);
        //cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
        pt = k.first - 1;
        if(macnt * k.second > cnt * ma) {
            //cout << "E1\n";
            macnt = cnt;
            ma = k.second;
            ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
        }
        if(pt < 0) break;
        if(macnt * Y[pt] > cnt * ma) {
            //cout << "E2\n";
            macnt = cnt;
            ma = Y[pt];
            ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
        }
        cnt *= X[pt];
        //cout <<pt << ' ' << ans << '\n';
    }
    return ans;
}
int updateY(int pos, int val) {
    tree.Edit(2, pos, val);
	Y[pos] = val;
    long long int cnt = 1;
    int pt = N;
    long long int macnt = 1;
    int ma = 0;
    int ans = 0;
    while(pt >= 0 && cnt <= 1e9) {
        P k = tree.get_left(pt);
        //cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
        pt = k.first - 1;
        if(macnt * k.second > cnt * ma) {
            //cout << "E1\n";
            macnt = cnt;
            ma = k.second;
            ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
        }
        if(pt < 0) break;
        if(macnt * Y[pt] > cnt * ma) {
            //cout << "E2\n";
            macnt = cnt;
            ma = Y[pt];
            ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
        }
        cnt *= X[pt];
        //cout <<pt << ' ' << ans << '\n';
    }
    return ans;
}

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 member function 'P SegTree::get_left(int)':
horses.cpp:75:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |             int mid = s + e >> 1;
      |                       ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:113:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  113 |     while(pt >= 0 && cnt <= 1e9) {
      |                      ^~~
horses.cpp:121:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |             ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:128:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |             ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:100:12: warning: unused variable 'j' [-Wunused-variable]
  100 |     int i, j;
      |            ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  143 |     while(pt >= 0 && cnt <= 1e9) {
      |                      ^~~
horses.cpp:151:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  151 |             ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:158:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |             ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:173:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  173 |     while(pt >= 0 && cnt <= 1e9) {
      |                      ^~~
horses.cpp:181:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  181 |             ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:188:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  188 |             ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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