제출 #483951

#제출 시각아이디문제언어결과실행 시간메모리
483951Cross_Ratio말 (IOI15_horses)C++14
100 / 100
477 ms34216 KiB
#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 n = k + MAX/2 - 1; if(k == 0) return P(k, 0); while(n) { //cout << n << ' '; if(seg1[n] != 1) break; while(n % 2 == 0) { n /= 2; } n ^= 1; } //cout << '\n'; if(n == 0) { return P(0, sum2(0, k)); } while(n < MAX/2) { if(seg1[2*n+1] != 1) n = 2*n + 1; else n = 2*n; } n -= MAX/2; n++; return P(n, sum2(n, 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) { 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) { macnt = cnt; ma = Y[pt]; ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p; } cnt *= X[pt]; } 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); pt = k.first - 1; if(macnt * k.second > cnt * ma) { 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) { macnt = cnt; ma = Y[pt]; ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p; } cnt *= X[pt]; } 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); pt = k.first - 1; if(macnt * k.second > cnt * ma) { 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) { macnt = cnt; ma = Y[pt]; ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p; } cnt *= X[pt]; } return ans; }

컴파일 시 표준 에러 (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;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...