# | 제출 시각UTC-0 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
36533 | szawinis | Garaža (COCI17_garaza) | C++14 | 1753 ms | 37736 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
using ll = long long;
const int N = 1 << 17;
int n, q, a[N], lb[2*N], rb[2*N];
ll t[2*N];
vector<pair<int,int> > pref[2*N], suff[2*N];
void build(int pos, int l, int r) {
lb[pos] = l; rb[pos] = r;
if(l == r) {
pref[pos] = suff[pos] = {{a[l], l}};
t[pos] = a[l] > 1;
return;
}
int mid = l+r >> 1;
build(pos<<1, l, mid);
build(pos<<1|1, mid+1, r);
// init t
t[pos] = t[pos<<1] + t[pos<<1|1];
// cout << pos << ' ' << l << ' ' << r << ' ' << t[pos] << endl;
for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
while(j >= 0 && __gcd(suff[pos<<1][j].fs, pref[pos<<1|1][i].fs) == 1) --j;
if(j < 0) continue;
ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
t[pos] += res;
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |