oj.uz

답안 #572127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572127 2022-06-03T17:45:18 Z beaconmc 말 (IOI15_horses) C++14
37 / 100
 406 ms 88212 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double
#define SIZE 1048576
#define HSIZE 524288
#define MOD 1000000007
// #include "horses.h"
using namespace std;

vector<ll> x, y, xx, yy;
ll n;


ll tree[SIZE];
ll tree2[SIZE];

set<vector<ll>> ranges;

void update(ll a,ll b){
    a += HSIZE;
    tree[a] = b;
    while (a>1){
        a/=2;
        tree[a] = tree[a*2]*tree[a*2+1]%MOD;
    }
}
void update2(ll a,ll b){
    a += HSIZE;
    tree2[a] = b;
    while (a>1){
        a/=2;
        tree2[a] = max(tree2[a*2], tree2[a*2+1]);
    }
}

ll query(ll a, ll b){
    a += HSIZE;
    b += HSIZE;
    ll maxi = 1;
    while (a<=b){
        if (a%2==1){
            maxi *= tree[a++]; 
            maxi %= MOD;
        }
        if (b%2==0){
            maxi *= tree[b--];
            maxi %= MOD;
        }
        a/=2; b/=2;
    }
    return maxi;
}
ll query2(ll a, ll b){
    a += HSIZE;
    b += HSIZE;
    ll maxi = 0;
    while (a<=b){
        if (a%2==1){
            maxi = max(maxi, tree2[a++]); 
        }
        if (b%2==0){
            maxi = max(maxi, tree2[b--]);
        }
        a/=2; b/=2;
    }
    return maxi;
}




int solve(){

	vector<ll> xx;
	vector<ll> yy;
	vector<ll> pos;

	ll cur = 30;
	auto it = ranges.end();

	while (cur--){
		it--;
		xx.push_back(x[(*it)[0]]);
		yy.push_back(query2((*it)[0], (*it)[1]));
		pos.push_back((*it)[0]);
		if (it==ranges.begin()){
			break;
		}
	}
	reverse(xx.begin(), xx.end());
	reverse(yy.begin(), yy.end());
	reverse(pos.begin(), pos.end());

	cur = 1;
	ll maxsum = 1;
	ll maxpos = -1;

	FOR(i,0, xx.size()){
		cur *= xx[i];
		if (yy[i] * cur >= maxsum){
			cur = 1;
			maxsum = yy[i];
			maxpos = i;
		}
	}


	return (query(0, pos[maxpos]) * maxsum) % 1000000007;
}

int init(int N, int X[], int Y[]) {
	n = N;
	FOR(i,0,N){
		x.push_back(X[i]);
		update(i, X[i]);
		y.push_back(Y[i]);
		update2(i, Y[i]);
	}
	ll prev = -1;

	FORNEG(i, n-1, -1){
		if (x[i] == 1 && prev==-1){
			prev = i;
		}

		if (x[i] != 1){
			if (prev != -1){
				ranges.insert({i, prev});
				prev = -1;
			}else{
				ranges.insert({i,i});
			}
		}
	}


	if (prev != -1){
		ranges.insert({0, prev});
	}


	return solve();

}

int updateX(int pos, int val) {
	if (x[pos] == val) return solve();
	update(pos, val);


	if (x[pos] == 1 && val != 1){
		auto it = ranges.upper_bound({pos, 999999999});
		it--;
		vector<ll> first = *it;
		ranges.insert({first[0], pos-1});
		ranges.insert({pos, first[1]});
		ranges.erase(it);
	}


	if (x[pos] != 1 && val == 1){
		auto it = ranges.upper_bound({pos, 999999999});
		it--;
		vector<ll> first = *it;
		it --;
		vector<ll> second = *it;
		ranges.erase(first);ranges.erase(second);
		ranges.insert({second[0], first[1]});

	}


	x[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	update2(pos, val);
	y[pos] = val;
	return solve();

}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:78:13: warning: declaration of 'xx' shadows a global declaration [-Wshadow]
   78 |  vector<ll> xx;
      |             ^~
horses.cpp:14:18: note: shadowed declaration is here
   14 | vector<ll> x, y, xx, yy;
      |                  ^~
horses.cpp:79:13: warning: declaration of 'yy' shadows a global declaration [-Wshadow]
   79 |  vector<ll> yy;
      |             ^~
horses.cpp:14:22: note: shadowed declaration is here
   14 | vector<ll> x, y, xx, yy;
      |                      ^~
horses.cpp:5:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  102 |  FOR(i,0, xx.size()){
      |      ~~~~~~~~~~~~~~              
horses.cpp:102:2: note: in expansion of macro 'FOR'
  102 |  FOR(i,0, xx.size()){
      |  ^~~
horses.cpp:112:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  return (query(0, pos[maxpos]) * maxsum) % 1000000007;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 396 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 312 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Runtime error 3 ms 696 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 362 ms 79420 KB Output is correct
2 Correct 406 ms 88212 KB Output is correct
3 Correct 386 ms 79408 KB Output is correct
4 Correct 392 ms 83352 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Runtime error 3 ms 700 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 312 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Runtime error 4 ms 852 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -