oj.uz

Submission #1025589

# Submission time Handle Problem Language Result Execution time Memory
1025589 2024-07-17T07:52:26 Z thdh__ Meteors (POI11_met) C++17
74 / 100
 449 ms 47528 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ff(x,a,b,c) for (auto x=a;x<=b;x+=c)
#define fd(x,a,b,c) for (auto x=a;x>=b;x-=c)
#define int ll

using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 3e5+5;
const int mod = 1e9+7;
const int INF = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

struct bit {
    int n,b[N];
    void init(int _)
    {
        n = _; 
        for (int i=1;i<=n;i++) b[i] = 0;
    }
    void upd(int x,int v)
    {
        for (;x<=n;x += x&(-x)) b[x] += v;
    }
    int get(int x)
    {
        int sum = 0;
        for (;x>0;x -= x&(-x)) sum += b[x];
        return sum;
    }
    void update(int l,int r,int v)
    {
        upd(r+1,-v), upd(l,v);
        if(l>r) upd(1,v);
    }
} BIT;

int n,m,k;
vector<int> o[N];
int p[N];
vector<array<int,3>> event;
int ans[N];

void PBS(int l,int r,vector<int>& mem)
{
    if (l==r-1 || !mem.size())
    {
        for (auto i : mem) ans[i] = l;
        return;
    }
    int mid = (l+r)/2;
    //calculate [l,mid]
    for (int i=l;i<mid;i++)
    {
        auto cur_event = event[i];
        int cl = cur_event[0],cr = cur_event[1],ca = cur_event[2];
        BIT.update(cl,cr,ca);
    }
    vector<int> p1,p2; // members in the first half and second half
    for (auto c : mem)
    {
        int sum = 0;
        for (auto i : o[c]) sum += BIT.get(i);
        if (sum >= p[c]) p1.pb(c);
        else p2.pb(c),p[c]-=sum;
    }
    //undo
    for (int i=l;i<mid;i++)
    {
        auto cur_event = event[i];
        int cl = cur_event[0],cr = cur_event[1],ca = cur_event[2];
        BIT.update(cl,cr,-ca);
    }
    PBS(l,mid,p1); p1.clear();
    PBS(mid,r,p2); p2.clear();
}

void solve()
{
	cin>>n>>m;
    BIT.init(m);
    for (int i=1;i<=m;i++) 
    {
        int x; cin>>x; o[x].pb(i);
    }
    for (int i=1;i<=n;i++) cin>>p[i];
    cin>>k;
    for (int i=0;i<k;i++) 
    {
        int l,r,a; cin>>l>>r>>a;
        event.pb({l,r,a});
    }
    vector<int> tmp;
    for (int i=1;i<=n;i++) tmp.pb(i);
    PBS(0,k+1,tmp);
    for (int i=1;i<=n;i++)
    {
        if (ans[i]==k) cout<<"NIE";
        else cout<<ans[i]+1;
        cout<<endl;
    }
}

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 3 ms 10732 KB Output is correct
3 Correct 4 ms 10584 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14036 KB Output is correct
2 Correct 87 ms 19912 KB Output is correct
3 Correct 77 ms 14276 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 14040 KB Output is correct
2 Correct 78 ms 14040 KB Output is correct
3 Correct 80 ms 18116 KB Output is correct
4 Correct 31 ms 13084 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13828 KB Output is correct
2 Correct 82 ms 18464 KB Output is correct
3 Correct 16 ms 12756 KB Output is correct
4 Correct 73 ms 14540 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13644 KB Output is correct
2 Correct 82 ms 14224 KB Output is correct
3 Correct 36 ms 13776 KB Output is correct
4 Correct 97 ms 17768 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 47528 KB Output is correct
2 Incorrect 201 ms 35020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 44464 KB Output is correct
2 Incorrect 192 ms 35268 KB Output isn't correct
3 Halted 0 ms 0 KB -