Submission #534102

#	Time	Username	Problem	Language	Result	Execution time	Memory
534102		Killer2501	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	103 ms	19488 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = 55;
const int mod = 998244353;
const ll base = 75;
const ll inf = 1e12+7;
int n, t, cnt, d[N], c[N], id[N], P[N][20];
int h[N], lab[N];

ll ans, tong, m, k, a[N], b[N];
vector<pii> adj[N];
vector<ll> vi;
vector<int> gr[N];
string s;
bool vis[N];
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n&1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
struct edge
{
    int x, y;
    ll w;
    edge(int _x, int _y, ll _w)
    {
        x = _x;
        y = _y;
        w = _w;
    }
    bool operator < (const edge& e)
    {
        return w < e.w;
    }
};
vector<edge> q;
int findp(int u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
bool hop(int u, int v)
{
    u = findp(u);
    v = findp(v);
    if(u == v)return false;
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
}
struct BIT
{
    int n;
    vector<pll> fe;
    BIT(){}
    void init(int _n)
    {
        n = _n;
        fe.assign(n+1, make_pair(inf, 0));
    }
    void add(int id, pll x)
    {
        for(; id <= n; id += id & -id)fe[id] = min(fe[id], x);
    }
    pll get(int id)
    {
        pll res = {inf, 0};
        for(; id; id -= id & -id)res = min(res, fe[id]);
        return res;
    }
};
pll p[N];
bool cmp(const int& x, const int& y)
{
    return (p[x].fi < p[y].fi) || (p[x].fi == p[y].fi && p[x].se < p[y].se);
}
void findegde()
{
    BIT bit;
    for(int j = 0; j < 4; j ++)
    {
        if(j == 2)for(int i = 1; i <= n; i ++)p[i].fi *= -1;
        if(j&1)for(int i = 1; i <= n; i ++)swap(p[i].fi, p[i].se);
        vi.clear();
        for(int i = 1; i <= n; i ++)vi.pb(p[i].fi-p[i].se);
        sort(vi.begin(), vi.end());
        vi.erase(unique(vi.begin(), vi.end()), vi.end());
        sort(id+1, id+1+n, cmp);
        bit.init(n);
        for(int i = n; i > 0; i --)
        {
            k = lower_bound(vi.begin(), vi.end(), p[id[i]].fi-p[id[i]].se) - vi.begin() + 1;
            pll res = bit.get(k);
            if(res.fi < inf)
            {
                tong = abs(p[id[i]].fi-p[res.se].fi) + abs(p[id[i]].se-p[res.se].se);
                q.pb(edge(id[i], res.se, tong));

            }
            bit.add(k, make_pair(p[id[i]].fi+p[id[i]].se, id[i]));
        }
    }
}

void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        b[i] = 1;
        while(a[i] % 2 == 0)
        {
            b[i] *= 2;
            a[i] /= 2;
        }
        b[i] += b[i-1];
    }
    cin >> m;
    while(m -- > 0)
    {
        cin >> k;
        int j = lower_bound(b+1, b+1+n, k) - b;
        cout << a[j] << '\n';
    }

}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:150:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:151:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40