Submission #922094

#	Time	Username	Problem	Language	Result	Execution time	Memory
922094		astilate	Meteors (POI11_met)	C++14	0 / 100	794 ms	30904 KiB

met

#include<bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define getint(n) int n; scanf("%d%*c", &n)
#define getll(n)  ll n; scanf("%lld%*c", &n)
#define inta int a; scanf("%d%*c", &a)
#define intab int a,b; scanf("%d%*c%d%*c", &a,&b)

#define forr(i, n) for(int i = 1; i <= (n); i++)
#define fors(i, s, e) for(int i = (s); i <= (e); i++)
#define fore(i, e, s) for(int i = (e); i >= (s); i--)

#define pb push_back
#define fi first
#define se second

#define prev _prev

using namespace std;

using ll = long long;
using pii = pair<int,int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vii=vector<pii>;

const int N = 3e5+7;
ll tree[N];
void update(int i, int x)
{
    while(i < N)
    {
        tree[i] += x;
        i += i&-i;
    }
}
void update(int l, int r, ll x)
{
    if(l < r)
    {
        update(l, x); 
        update(r+1, -x);
    }
    else
    {
        update(1, x); update(r+1, -x);
        update(l, x);
    }
}

ll query(int i)
{
    ll ret = 0;
    while(i) ret += tree[i], i-=i&-i;
    return ret;
}

vi arr[N]; vector<pair<pii, int> > q;
int ans[N]; int p[N];
void solve()
{
    getint(n); getint(m);
    forr(i, m)
    {
        getint(a);
        arr[a].pb(i);
    }
    forr(i, n) scanf("%d", p+i);
    getint(Q);
    forr(i, Q)
    {
        getint(l); getint(r); getint(a);
        q.pb({{l, r}, a});
    }
    
    vii now;
    int st = 20;
    while(st+1)
    {
        forr(i, n) if(ans[i]+(1<<st) <= Q) now.pb({ans[i]+(1<<st), i});
        st--;
        
        sort(all(now));
        
        auto it = now.begin();
        forr(i, Q)
        {
            auto [l, r] = q[i-1].fi;
            auto a = q[i-1].se;
            
            update(l, r, a);
            
            while(it != now.end() and it->fi == i)
            {
                ll x = 0;
                for(auto c : arr[it->se])
                    x += query(c);
                
                if(p[it->se] > x) ans[it->se] = it->fi;
                it++;
            }
        }
        
        now.clear();
        memset(tree, 0, sizeof tree);
    }
    
    forr(i, n)
    {
        if(ans[i] == Q) printf("NIE\n");
        else printf("%d\n", ans[i]+1);
    }
}
int main()
{
    //while(true)
        solve();
}

Compilation message (stderr)

met.cpp: In function 'void solve()':
met.cpp:88:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |             auto [l, r] = q[i-1].fi;
      |                  ^
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:62:5: note: in expansion of macro 'getint'
   62 |     getint(n); getint(m);
      |     ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:62:16: note: in expansion of macro 'getint'
   62 |     getint(n); getint(m);
      |                ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:65:9: note: in expansion of macro 'getint'
   65 |         getint(a);
      |         ^~~~~~
met.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     forr(i, n) scanf("%d", p+i);
      |                ~~~~~^~~~~~~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:69:5: note: in expansion of macro 'getint'
   69 |     getint(Q);
      |     ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:72:9: note: in expansion of macro 'getint'
   72 |         getint(l); getint(r); getint(a);
      |         ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:72:20: note: in expansion of macro 'getint'
   72 |         getint(l); getint(r); getint(a);
      |                    ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:72:31: note: in expansion of macro 'getint'
   72 |         getint(l); getint(r); getint(a);
      |                               ^~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13