oj.uz

Submission #803852

# Submission time Handle Problem Language Result Execution time Memory
803852 2023-08-03T06:17:54 Z moel_solution(#10136) Vera and Modern Art (CCO17_art) C++17
5 / 25
 2013 ms 93744 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int lst[200010][60];
ll ans[200010];
vector<int>idlst[200010];
vector<pi>smlst[200010];
ll sum[200010];
int idx(const vector<ll>&v,ll y)
{
    auto it=upper_bound(all(v),y)-v.begin();
    if(it!=0&&v[it-1]!=y)
        it=0;
    return it;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<ll>cvx,cvy;
    vector<pair<pl,ll> >nv(n);
    for(auto&t:nv)
        cin>>t.fi.fi>>t.fi.se>>t.se,
        cvx.eb(t.fi.fi),
        cvy.eb(t.fi.se);
    sort(all(cvx));
    cvx.erase(unique(all(cvx)),cvx.end());
    sort(all(cvy));
    cvy.erase(unique(all(cvy)),cvy.end());
    for(auto&t:nv)
        t.fi.fi=idx(cvx,t.fi.fi),
        t.fi.se=idx(cvy,t.fi.se);
    for(auto&t:nv)
        smlst[t.fi.fi].eb(t.fi.se,t.se);
    vector<pl>qv(q);
    for(pl&t:qv)
        cin>>t.fi>>t.se;
    for(int i=0;i<q;i++)
    {
        for(int j=0;j<60;j++)
        {
            ll d=1ll<<j;
            if(qv[i].fi<d)
                break;
            ll cur=d+(qv[i].fi&(d-1));
            int id=idx(cvx,cur);
            if(id!=0)
                idlst[id].eb(i);
        }
        for(int j=0;j<60;j++)
        {
            ll d=1ll<<j;
            if(qv[i].fi<d)
                break;
            ll cur=d+(qv[i].se&(d-1));
            lst[i][j]=idx(cvy,cur);
        }
    }
    for(int i=0;i++<(int)cvx.size();)
    {
        for(pi&t:smlst[i])
            sum[t.fi]+=t.se;
        for(int&id:idlst[i])
            for(int j=0;j<60;j++)
                ans[id]+=sum[lst[id][j]];
        for(pi&t:smlst[i])
            sum[t.fi]-=t.se;
    }
    for(int i=0;i<q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 9 ms 10452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 80356 KB Output is correct
2 Correct 522 ms 80360 KB Output is correct
3 Correct 2013 ms 93744 KB Output is correct
4 Correct 2001 ms 93684 KB Output is correct
5 Correct 1203 ms 89008 KB Output is correct
6 Correct 1149 ms 89104 KB Output is correct
7 Correct 1139 ms 89004 KB Output is correct
8 Correct 1194 ms 89100 KB Output is correct
9 Correct 1181 ms 89124 KB Output is correct
10 Correct 1142 ms 89012 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 281 ms 45732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 9 ms 10452 KB Output isn't correct
3 Halted 0 ms 0 KB -