QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#560185#9250. Max GCDduckindogCompile Error//C++232.1kb2024-09-12 14:05:362024-09-12 14:05:37

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 14:05:37]
  • 评测
查看
  • [2024-09-12 14:05:36]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#include <bits/stdc++.h>

using namespace std;

const int N = 150'000 + 10,
          MAX = 1'000'000;
int n, q;
int a[N];
struct Query { 
  int l, r, idx;
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.l >> rhs.r;
  }
} query[N];
int answer[N];

vector<int> pos[MAX + 10];
vector<pair<int, int>> save[N];

int bit[N];
void upd(int i, int x) { 
  for (; i <= n; i += i & -i) bit[i] = max(bit[i], x);
}
int que(int i) { 
  int ret = 0;
  for (; i; i -= i & -i) ret = max(ret, bit[i]);
  return ret;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= q; ++i) cin >> query[i], query[i].idx = i;

  for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i); 

  { //init
    set<pair<int, int>> s;
    for (int value = MAX; value >= 1; --value) { 
      vector<int> totalPos;
      for (int multiple = value; multiple <= MAX; multiple += value) { 
        for (const auto& x : pos[multiple]) totalPos.push_back(x);
      }
      if (totalPos.size() <= 2) continue;

      sort(totalPos.begin(), totalPos.end());
      for (const auto& x : totalPos) { 
        if (x == totalPos[0] || x == totalPos.back()) continue;

        int l = *(lower_bound(totalPos.begin(), totalPos.end(), x) - 1),
            r = lower_bound(totalPos.begin(), totalPos.end(), 2 * x - l) - totalPos.begin();
        if (r == totalPos.size()) continue;
        r = totalPos[r];
        
        if (!s.count({l, r})) { 
          s.insert({l, r});
          save[l].push_back({r, value});
        }
      }
    }
  }

  sort(query + 1, query + q + 1, [&](const auto& a, const auto& b) { return a.l < b.l; });

  int it = n;
  for (int i = q; i >= 1; --i) { 
    const auto& [l, r, idx] = query[i];

    while (it >= l) 
      for (const auto& [r, value] : save[it--]) upd(r, value);

    answer[idx] = que(r);
  }

  for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";

  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}
源文件, 语言: C++23

詳細信息 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:3:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

伺服器時間: 2024-11-30 02:38:49 | 開源專案